Douglas_Knight comments on Can somebody explain this to me?: The computability of the laws of physics and hypercomputation - Less Wrong

12 Post author: ChrisHallquist 21 April 2013 09:22PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (53)

You are viewing a single comment's thread. Show more comments above.

Comment author: Douglas_Knight 22 April 2013 10:35:54PM 1 point [-]

Infinite time is not enough to do hypercomputation. You also need infinite memory. If you only have n bits of memory, you only have 2^n possible states, so after time 2^n, your computation must terminate or have entered a loop, so more time is not useful.

Also, your and wikipedia's description is pretty vague. Deutsch proposed a more precise model of computation along a CTC. It assumes that you only have finitely many bits of memory (and thus are computable), but it avoids the problems that shminux mentions. John Watrous and Scott Aaronson proved that in this model, you can take full advantage of the time and compute full PSPACE problems. While such problems are not supposed to be tractable in short time without a CTC, that's a far cry from halting. Also, reversible computing should make PSPACE problems practical in some sense.