Can a Turing machine be constructed having only two tape symbols?

Question

A Turing machine M containing any number of tape symbols can be simulated by one M' containing just three tape symbols: {0, 1, B} (B = Blank).

Can M be be simulated by a M" that has just two tape symbols, say {1, B}?

Answer 1

The first step - getting from any TM to a TM with just ones and zeros - is not as hard as you might think but not as easy as what everyone else is saying. The idea is to develop a fixed-length binary encoding for each of the symbols in the alphabet. You then update the finite-state control so that at each step the TM scans the appropriate number of bits, decides which way to move and which symbol to write, writes the binary representation of the new symbol, and repeats. This can be done by having a HUGE finite-state control, and I'll leave the details to the reader since it's really pedantic to go over how it works. :-). The one detail to note is that in this construction you represent the blank symbol as a sequence of blanks with the same length as the binary symbols you invented.

To implement a TM using just 1 and B you use a similar trick. First, reduce the TM to use just 1, 0, and B. We'll again reduce the symbol set by a smaller one, but will have to be a bit more clever with how we do so because the tape has infinitely many blanks on it. We will use the following encoding:

1. 11 encodes the number 1
2. 1B encodes the number 0
3. BB encodes a blank.

As we run the TM using this encoding scheme, if we ever walk past the end of the previously-visited tape, we will encounter infinitely many blank symbols, which fortunately correspond to our encoding of the blank symbol.

The only challenge is how to encode the input to this new TM so that we can convert it to this above format. Since blanks can't appear in the TM input, the input must be encoded in unary. We then stipulate that for any binary string w of the old machine, the input to the new machine should be the unary encoding of the number 1w. We then have the first step of the machine be to convert from the unary encoding to the above binary encoding. This can be done with just two symbols, but the details are really hard and again I'm going to punt on them. You can work out the details if you want.

Hope this helps!

Answer 2

The first one is easy, think of a computer, binary....

In the first one you can encode each symbol into a 0,1 representation.

In the second one, you can do 2 things:

1. Think of the B as 0 ... it doesn't matter what you call it... and then you have a 0,1 machine and can encode whatever you want.

2. Encode the symbols as a series of ones, separated by a B. The N'th symbol will hold N 1's