Cheap and Secure Web Hosting Provider : See Now

[Solved]: Turing Machines: Arbitrary alphabet equivalence with binary alphabet

, , No Comments
Problem Detail: 

Think of an $n$-ary alphabet as $\{0, 1, ..., n-1, n\}$. For example, a binary alphabet is $\{0, 1\}$.

Do Turing Machines with binary alphabets decide the same set of languages as Turing Machines with $3$+ symbol alphabets?

I am unsure of how to show equivalence. Clearly, any $3$+ symbol TM can simulate a TM with $2$ symbols, but I don't know how to show the other direction (if one exists).

Asked By : Ryan

Answered By : usul

I am answering the question "Can Turing Machines with binary alphabet decide the same languages as Turing Machines with 3 or more alphabet symbols?"

Now, on the one hand, it's not well-defined what happens if you take a string with three different alphabet symbols and give it to a TM that only is designed to see a binary alphabet on the tape. So in that sense, a three-symbol Turing Machine can decide languages with these strings, while the two-symbol machine isn't allowed to read them. (For instance, if the language has "a", "b", and "c" in it, then there is no TM with a binary alphabet that reads these strings.)

But you might ask this question instead. Let's consider only languages whose strings have two symbols, in order to give a fair comparison between the two-symbol TM and the three-symbol TM. Now, can the three-symbol TM decide more of these languages, simply because it can write more types of symbols on the tape while it is computing?

The answer here is "no". The idea is that we have to take any three-symbol Turing Machine and show that there is a two-symbol TM that essentially takes the same "steps" and accepts whenever the original one accepts, etc. Just as a hint, the idea here is to make a TM with a modified transition table so that it can "act like" it's writing the third symbol down, even though it's only using two symbols.

Best Answer from StackOverflow

Question Source :

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback