2
$\begingroup$

Brief context:

I'm trying to understand why a Universal Turing Machine exists, on a tape with alphabet $\{0, 1\}$. I think I can see that a $3$-tape Turing machine can represent a Universal Turing Machine, using tape $1$ for the input corresponding to the Turing machine to simulate, tape $2$ corresponding to a buffer containing the current state, and tape $3$ being the actual computation on the input.

So this reduces to understanding why any function computable by a multi-tape Turing machine is also computable by a single-tape Turing machine.

Now, by adding in extra possible symbols to my alphabet, I can see how I could simulate a multi-tape Turing machine with a single-tape Turing machine with a larger alphabet (something like: Add in a delimiter '#' to separate the tapes, and symbols $\dot{0}, \dot{1}, \dot{B}$ to represent the current position on each tape). However, it's not clear to me how it would be possible to do this on a tape where we're only allowed the alphabet $\{0, 1\}$.

My question is:

Given a Turing machine $T$ on some (finite) alphabet $\Sigma \supseteq \{0, 1\}$ that calculates a partial function $\mathbb{N} \to \mathbb{N}$ (using the binary representation), does there exist a Turing machine $T'$ just on the alphabet $\{0, 1\}$ that calculates the same partial function?

(This then answers the last part of my thought process above.)

$\endgroup$
  • $\begingroup$ Thanks! I knew I wasn't sure about the correct names for things - I'll edit the question. $\endgroup$ – ECG Nov 28 '15 at 18:20
  • 1
    $\begingroup$ Yes you can encode symbols of $\Sigma$ as strings of $0$s and $1$s of fixed length $\lceil \log_2 \lvert \Sigma \rvert \rceil$ and define $T'$ from $T$ to operate on these binary chunks. $T'$ needs more states than $T$ to remember $T$'s state and figure out what symbol it has scanned... and other details. But it can be done. $\endgroup$ – BrianO Nov 28 '15 at 18:25
  • $\begingroup$ Oh good (re thanks & edit), I was hoping that would be your response. Some people... are not like that, lol. You're very welcome. $\endgroup$ – BrianO Nov 28 '15 at 18:27
2
$\begingroup$

It is certainly possible for a Turing machine with alphabet $\{0,1\}$ to simulate a Turing machine with any finite alphabet. The idea is that if the larger alphabet has size less than $2^k$ then you can divide the tape into "chunks" of size $k$ and use each of these chunks to encode a single character from the larger alphabet. This requires a larger number of states in the new machine, because recognizing a single symbol from the larger alphabet requires a sequence of $k$ states in the new machine.

This is slightly analogous to using UTF-32 to store strings of arbitrary Unicode characters in a programming language that only supports 8-bit characters.

$\endgroup$

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.