A string representation of any Turing machine

Problem Detail: 

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble seeing how this could be true.

If we formally define a Turing machine as having a tape language $\{0, 1, \sqcup, x\}$ and input language $\{0, 1\}$, then I can sort of see how any Turing machine could be encoded.

However, many books allow other symbols, such as $a$ or $3$, etc., to be part of the input language. I've heard people say that this is okay because we could represent such characters as a string like $0101$ or $1011$ or whatever, much like how Unicode represents code points consisting of multiple code units, or just how any computer represents anything at all!

But here is my problem with this. If we are trying to construct an actual function $f$ from the set of all Turing machines $\mathscr{M}$ to $\mathbb{N}$, then every Turing machine must be encoded in the same way. That is, we can't have encodings of different lengths, so that 01 represents $01$ for one Turing machine and represents $3$ for another. That is, unless we have some encoding at the beginning of each Turing machine which explains how the machine is to be decoded. But even then, this encoding itself must be universal.

The problem is much like the charset problem for HTML pages. That is, that a web browser must know the encoding of the page before it can decipher a command in the HTML to encode the page a certain way. This was solved for web pages by having the encoding command characters (meta charset=utf-8 for example) be the same in all encodings. But then the encoding itself is stored elsewhere.

Anyway, my question is how we resolve this apparent conundrum. How does one encode a Turing machine with a finite input language of any length so that one can make one function from $\mathscr{M}$ to $\mathbb{N}$?

Asked By : AmadeusDrZaius

Answered By : Yuval Filmus

Consider a Turing machine with $n$ tape symbols and $m$ states. We can assume that the symbols and the states are ordered, so that we can talk about the first, second, ..., $n$th tape symbol, and the first, second, ..., $m$th state. (This is similar to your idea of counting Turing machines up to isomorphism.) So without loss of generality, the tape alphabet is $\{1,\ldots,n\}$ and the states are $\{1,\ldots,m\}$. We will encode this Turing machine as the following sequence of statements in English: (the notation $\langle n \rangle$ means to replace $n$ with its decimal representation)

• The number of tape symbols is $\langle n \rangle$.
• The number of states is $\langle m \rangle$.
• The starting state is $\langle s_0 \rangle$. [Replace $s_0$ with the starting state]
• The accepting states are $\langle s_1 \rangle$, ..., $\langle s_k \rangle$. [Replace $s_1,\ldots,s_k$ with the accepting states]
• When in state 1, upon reading symbol 1, write symbol $\langle \sigma \rangle$ and move $\langle D \rangle$ [Replace $\sigma$ with the tape symbol and $D$ with either "left" or "right"]
• ...

This is a description in English over a finite alphabet. In particular, it can be represented in ASCII. So there are only countably many descriptions.

---

As usul mentions, we tacitly assume that the underlying representation of everything in mathematics is a set, just like the description of everything in computers is in binary. Not all sets are finite, but if you only use hereditarily finite sets, then you can avoid forcing the tape alphabet to be $\{1,\ldots,n\}$, and instead allow arbitrary hereditarily finite sets. However, that doesn't buy you anything (unless you care about this point for philosophical reasons).

More generally, you might be worried that when I describe a Turing machine I use the symbol $\diamond$, a symbol not covered by the above (it's a set-theoretic "atom"), so this Turing machine doesn't have a description in my formalism. To counter this, I suggest you provide the description of your Turing machine as a LaTeX document (which is what I used when describing the machine in the first place). LaTeX has a finite alphabet (or finitely many possible finite alphabets), so again everything is countable.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22169