0

You sometimes see claims that no Turing machine exists which solves a particular problem, for example, no Turing machine exists which, given an arithmetic statement, outputs correctly either "true" or "false" (according to the accepted answer here).

But what confuses me is that this statement doesn't seem to define what "given an arithmetic statement" means, because Turing machines accept strings of symbols as input, and there isn't a single "correct" way to specify arithmetic statements as strings of symbols.

Indeed, since there are countably many arithmetic statements, of which countably many are true and countably many are false, we could simply have a Turing machine output "true" for even numbers and "false" for odd ones. For some encoding of arithmetic statements as integers, this is the Turing machine that is claimed not to exist.

So clearly, statements of the form "The problem $P$ cannot be solved by a Turing machine" are missing some implicit criteria for how the problem is to be formatted for input. What would a completely detailed statement of such an unsolvability theorem look like?

Community
  • 1
Jack M
  • 27,819
  • 7
  • 63
  • 129
  • The easiest result to prove is for a specific encoding. The second easiest is for encodings that are recursively equivalent to the specific encoding. – André Nicolas Oct 21 '15 at 17:57
  • If you have two equivalent theorems $\mathbf{A}$ and $\mathbf{B}$, and you can prove $\mathbf{A} \Rightarrow \mathbf{B}$ and $\mathbf{B} \Rightarrow \mathbf{A}$ then it's said the two theorems are equivalent. Likewise, for any two coding methods, if you can create Turing-machine algorithms to translate from each to the other, then anything accomplished by a Turing machine using coding method A can be accomplished by another Turing machine using coding method,B, but with translation phase added. So all sufficiently powerful coding methods are equivalent. – NovaDenizen Oct 21 '15 at 18:52
  • You might also want to read Turing's paper where he details the construction of a machine in his halting problem proof. – NovaDenizen Oct 21 '15 at 18:55

1 Answers1

2

You're right - in the background, there's always a coding assumption. E.g., if the inputs to our problem are finite strings of naturals, then we have to fix at the outset some way of coding finite strings of naturals as finite strings of 1s (if that's how we're inputting things to our Turing machine - there are many models of course).

Why is this suppressed? Well, actually, what we prove in these cases is very coding-independent: as long as you come up with a method of coding which isn't "silly", you'll get the same result. This can be formalized by proving that any coding satisfying a couple basic properties yields the same result, and these proofs usually aren't more than one or two lines longer than the initial undecidability proof they stem from. In spirit, this suppression of coding method is very similar to appeals to Church's thesis - at that stage in the game, you're expected to be able to fill in the details, and prove the appropriate generalizations, yourself. This may well be bad pedagogy in many cases, but it's what's going on.

Noah Schweber
  • 245,398