# Turing Machines: Arbitrary alphabet equivalence with binary alphabet

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

• 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? – usul Feb 7 '15 at 2:52
• 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?" – usul Feb 7 '15 at 2:55
• @usul in your second comment, that's what I meant to ask. Thanks! – Ryan Feb 7 '15 at 2:59
• 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. – usul Feb 7 '15 at 4:19
• 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! – D.W. Feb 7 '15 at 7:02