Computability in Classical Physics

[klen]

I was reading the book "Emperor's New Mind" by Roger Penrose which deals with understanding the nature of mind in the sense that it is algorithmic or not. In one of the chapters he explains that the deterministic world of the Newtonian Theory can still be non-computable. He explains this as follows:
Assuming that the state of universe can be described by a pair of natural numbers (m,n) then, if the universe is computable there would be a turing machine which would compute the state at the next instant. Let the universal turing machine U be imitating this machine. Then, if the machine acting on m i.e., U(m) stops the next state would be (m+1,n) and if U(m) does not stop, the next state would be (n+1,m). Since we cannot determine if the machine U will stop or not algorithmically, we conclude that the universe is non-computable though it is deterministic.

Can anyone explain me how do we conclude the next state using the above argument. In particular, why is next state (m+1,n) if U(m) stops?

 

[nomadreid]

I do not know whether Penrose offers his formulation of a Turing machine (there are many possible equivalent formulations) in that book, so I can only guess. He appears to have a simple binary tree, in which there are two choices at each node as the results of the action of U on m: left, stop, or right, continue.
First, we could use ordered pairs: you would have (m,n) going either to (m+1,n) when it goes to the left, and (m, n+1) when it goes to the left. However, if you know what m is in the U(m), as well as what the two original numbers were, then there is no need for an ordered pair, since you could figure it out from knowing the m in U(m) and the (m,n) as the original state.
As a side note: when you get to his Gödelian argument, take it with a huge grain of salt. Otherwise put, it's wrong. Feferman and others have done a nice job of dismantling the argument (which is just the argument given by Lucas, spruced up a little).

 

[chiro]

You might want to consider that the Turing model is not the only form of computation.

You can construct forms of computation that you know to terminate but you have to place heavy restrictions on the constraints of "code" that you allow along with the data within said code.

For example - you can construct code that continually stays within a loop and in a Turing based analysis it certain does hold that there are times when you are unable to know whether something halts or doesn't.

But it's a bad idea to be so specific when looking at computational complexity and computer science just as it is bad to look at something like language and logic in an unrestricted sense.

In logic there are ways to create internal inconsistencies with language and logical relations and the area of mathematical logic is full of examples like the barbers paradox, the liars paradox, and even the famous theorems on incompleteness.

What you do to avoid such inconsistencies is you place constraints on what you allow. This means for language you constraint the vocabulary, the grammatical structure and the sentences that you can create. For logic this means constraining the logical relations you can use so that they create the right predicates to be consistent along with constraining the classes of variation that describe the representation that the logic applies itself to.

In computation you constrain the sorts of computations, data structures and representations of variation as pertaining to those data structures so that you can guarantee that anything within that class has a solution in that computational framework given some sort of computational complexity limit.

The Turing model is about as good as looking at language in an unconstrained form (which is to say it's not that useful) and you should really look at computational models that look at constraints that allow definitive solutions to be found given some upper bound of computational complexity.