0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ I think we have to carefully define some things to answer the question. First, what is the encoding we are using for the TMs? (And what is the alphabet for the languages $L_2$ and $L_{>2}$?) Second, what exactly does it mean to have symbols in a TM's alphabet? $\endgroup$ – usul Feb 7 '15 at 2:52
  • 1
    $\begingroup$ But is this really the question you want to ask? Or did you want to ask the following: "Do Turing Machines with binary alphabets decide the same set of languages as Turing Machines with 3+ symbol alphabets?" $\endgroup$ – usul Feb 7 '15 at 2:55
  • $\begingroup$ @usul in your second comment, that's what I meant to ask. Thanks! $\endgroup$ – Ryan Feb 7 '15 at 2:59
  • 1
    $\begingroup$ OK, these are very different! Your question as currently stated is about two particular languages. These are just sets of strings, just two particular languages. Instead you really wanted to ask about computational models and all possible languages they decide. You should try to understand the difference between that and your question, and edit the question to what you want to say! In the meantime I'll post an answer. $\endgroup$ – usul Feb 7 '15 at 4:19
  • $\begingroup$ Ryan, Please edit the question to match what you wanted to ask. As it stands you are likely to get answers to the question you wrote rather than the question you wanted to ask. You can click the "edit" link underneath your question to edit it. Thank you! $\endgroup$ – D.W. Feb 7 '15 at 7:02
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

We need to emulate an n-symbol Turing machine with a binary TM (the other direction is trivial). So you need to convert the input string to binary (e.g. usual binary encoding) and convert the transition function to work with the binary alphabet. E.g. you have a transition (F,T,R,M,W) - F = from state, T = to state, R = read symbol, M - move left/right, W = write symbol. You need to convert this to a sequence of transitions: first read the binary representation - use n states for that. Then you can move the head - log2(n) operations, then write the output, again use n states, then transition to T'.

$\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.