[Math] Alphabets of Turing Machine

automatacellular automataturing-machines

I'm not completely sure about equivalence of two definitions of Turing machine.

  • The first one states that Turing machine has a finite alphabet $\Sigma$, set of states and some rules.

  • Turing machine in the second definition has two alphabets – input one $\Sigma_1$ and working one $\Sigma_2$ and set of states and rules.

I think it doesn't matter which definition you use, but I didn't find any proof or at least some mention about it anywhere.

The biggest "problem" I have is when you prove that multi-tape Turing machine is equivalent to one-tape Turing machine because in the proof you extend the alphabet (for example here). When you use the second definition you extend just the working alphabet and everything is ok. When you have the first definition you have to extend the "input" alphabet so the modified one-tape Turing machine accept more languages than the original multi-tape one and they are not equivalent…

Do you know where this problem (equivalence of the two definitions) is discussed? Or can you explain me that it does not matter?

Best Answer

We'll first proof that a Turing Machine with a finite alphabet of size $n$ can be reduced to a Turing Machine with a finite alphabet of size 2 (with more stats, of course)

Give each of the symbols a binary code of length $\lceil \log_2 n \rceil$ and split each cell to $\lceil \log_2 n \rceil$ subcells, which will be the cells of the new Turing Machine.

For each state, we need $2^{\log_2 n}$ states to read the symbol. Then we decide what symbol to write per state. This takes $n \log_2 n$ states. Then moving to another state takes another takes $2 \log_2 n$ states.

The exact number doesn't matter, what matters is that we can reduce it.
More detail on this you can read here.

Note that a Turing machine with alphabet $\Sigma_1 \cup \Sigma_2$ is at least as strong as the second Turing machine in your question. But this Turing machine is equivalent to the Turing machine with alphabet size 2, which is in turn equivalent to the Turing machine with alphabet $\Sigma$.

I hope this answers your question.

Related Question