MrMind 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.

Comment author: MrMind 22 April 2013 09:21:56AM 1 point [-]

is there any chance it's possible to build a physical device that answers questions a Turing machine cannot answer?

Since any finite set is trivially computable, it only makes sense to talk about hypercomputation for infinite sets/functions. For example, a certain kind of infinite time Turing machine can solve the halting problem of every other finite time Turing machine.
This would mean that to physically realize a hypercomputer the universe has to allow finite access to infinite quantity (e. g. an infinite precision measurable real value, an infinite time pocket universe, etc). There are highly idealized model that does such things in both newtonian mechanics and general relativity, but they are not applicable to our universe.
Hypercomputation is a (set of) well defined mathematical model(s), so the question of its realizability is ultimately a physical one: at the present time knowledge we have about our universe rules out such models, but of course we cannot show that this continues to be valid in possible extensions.