> what does it mean to say Peano arithmetic is Turing complete? It means that fo... | Hacker News

It means that for any TM described by a state transition table X which produces output Y when run on tape Z, there exists a corresponding theorem of PA that encodes that fact under a suitable mapping from X, Y and Z to natural numbers. UPDATE: The converse is also true: for any theorem of PA there exists a TM that produces a proof of that theorem. The interesting bit here is that there is one TM that does this for any theorem of PA. And note that this machine is not the same as the universal TM that emulates any other TM. UPDATE2: The way I worded that was a little misleading. There are many TM's that produce a proofs of theorems of PA, but you only need one of them to produce any proof you want. Of course, the universal TM is one of the machines that can be deployed for this task.

It means that for any TM described by a state transition table X which produces output Y when run on tape Z, there exists a corresponding theorem of PA that encodes that fact under a suitable mapping from X, Y and Z to natural numbers. UPDATE: The converse is also true: for any theorem of PA there exists a TM that produces a proof of that theorem. The interesting bit here is that there is one TM that does this for any theorem of PA. And note that this machine is not the same as the universal TM that emulates any other TM. UPDATE2: The way I worded that was a little misleading. There are many T