4
$\begingroup$

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}$?

$\endgroup$
  • $\begingroup$ I just found this answer which addresses my question to some degree: cs.stackexchange.com/a/14518/12588. It claims that the statement really should be that there are only countably many Turing machines up to isomorphism. Is that correct? Also, on a related note, how are alphabets such as $\{a, b, c, \ldots\}$ defined formally within the confines of (ZFC) set theory? Are they just informal notations for numbers like $\{1, 2, 3, \ldots\}$? I guess where I'm getting confused is with the level of formality in the definition of a Turing machine. I know that (continued in next comment) $\endgroup$ – AmadeusDrZaius Mar 1 '14 at 22:36
  • $\begingroup$ (continued from previous comment) ... mathematics is more than rigor and notation, but we also have to be careful that the level of rigor we adopt is appropriate to the technicality of the question being answered. With regard to languages, the looseness of the idea of alphabets seems overly lax compared to the exactness of the question of countability. $\endgroup$ – AmadeusDrZaius Mar 1 '14 at 22:37
  • $\begingroup$ en.wikipedia.org/wiki/Prefix_code $\;$ $\endgroup$ – user12859 Mar 1 '14 at 22:56
  • $\begingroup$ Yes, your question is almost exactly a duplicate of the one you link and the answers there are correct. $\endgroup$ – usul Mar 1 '14 at 22:57
  • $\begingroup$ In ZFC, everything is a set, so $a$ and $b$ are names for sets that are "unique" (the only set with the same contents as $a$ is $a$). But it really doesn't matter for our purposes; just think of them as the symbols $a$ and $b$. The isomorphism is primarily to equate all alphabets of a given fixed number of characters, e.g. if it has four characters then the alphabet is isomorphic to $\{a,b,c,d\}$. $\endgroup$ – usul Mar 1 '14 at 23:00
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Duh. How could I forget that by talking about the Turing machine in the first place, we were doing so with a finite alphabet?! The answer seems obvious now, but it was exactly what I was missing. You explained it very well. Thank you. $\endgroup$ – AmadeusDrZaius Mar 1 '14 at 23:40
  • $\begingroup$ And +1 for using LaTeX as a proof of countability. $\endgroup$ – AmadeusDrZaius Mar 1 '14 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.