Can you write a Turing machine in set theory?

948 Views Asked by At

Let $T$ be a Turing Machine. Let us define $S$ as the set containing the result of the turing machine calculation. Then presumably this is expressable in terms of ZFC set theory. Since the result of a calculation is just a (or pair) binary number(s) which can be represented as some set.

But what would this set be if the Turing machine never stopped?

Would the set be ill-defined? Hence this leaves me to believe that expressing a Turing machine in (typed) set theory is forbidden?

1

There are 1 best solutions below

2
On BEST ANSWER

If the Turing machine calculation might not terminate, then the set containing the result is indeed not defined. But that's no fault of set theory (on the contrary, things are working exactly as they should be), nor is it any indication that set theory is somehow unable to formalize the idea of turing machines.

When you write down a definition, it is incumbent on you to show that it is actually a definition. "Let $x=12$ if the Goldbach conjecture is true" cannot be shown to be a valid definition since we don't know if the Goldbach conjecture is true. "Let $x=12$ if the Goldbach conjecture is True, otherwise let $x=10$", is a valid definition regardless cause we've covered both options. Similarly, "let $x$ be the output of the 147th turing machine on input 5" is not necessarily a definition unless we know that the 147th turing machine halts on input 5. If we don't, we better say what $x$ is in the event that it doesn't halt.

(It might be easier to see this if we try to define a function instead. Let $f(n)=0$ if $n$ can be written as the sum of two squares. This is not a definition of a (total) function cause we haven't said what happens if $n$ is not the sum of two squares. This doesn't mean set theory, or arithmetic, or whatever, is incapable of handling numbers.)

Nothing changes in the situtation where we say "let $S$ be the singleton set containing the output of the 147th Turing machine on input 5"... this simply is not necessarily a definition.

Turing machines can certainly be defined in set theory. You can define the internal state they are in and the location of the tape head as simple recursive functions. You can express things like "at computational step $n,$ the turing machine is in state $i$" as sentences in the language of set theory. You can express "the turing machine halts with output $m$" as "there is an $n$ such that at step $n$, the turing machine is in one of its halting state, and the output tape at this time contains the number $m$". You can express anything you want about a given turing machine on a given input, or about all turing machines, on all inputs, or whatever.

And there is nothing inherently set theoretical about it either: all these things can be encoded (perhaps somewhat less elegantly) as numbers and then you can talk about Turing machines in the language of arithmetic. You can prove more things in ZFC than in PA (for instance, there is a TM that halts if and only if PA is inconsistent... this can be proven to not halt in ZFC but not in PA), but the 'natural arena' for formalizing the mathematics of Turing machines is in arithemetic, not set theory.