I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7), ennary (base 9) or even decimal (base 10).

One programmer commented that Turing machines are always binary because the tape includes at least one stage to go to and at least one stage to go back to (or something of that sort; translating from Hebrew without knowing the professional terminology in English).

Must a Turing machine tape be binary? --- Can't it be unary in any situation?
Was there an attempt to create a "similar" model which is unary just for the sake of research (putting efficiency aside)?

  • 2
    $\begingroup$ You can have any number (positive integer) of alphabet symbols to write on the tape. $\endgroup$
    – plop
    Jan 29 at 16:21
  • $\begingroup$ Computers think in binary for ease of implementation (0/1 is easier to model in the "language" of voltages). Also, unary alphabet is discouraged because words would be exponentially longer than corresponding binary/d-ary's. The only "use" of unary alphabet that I know is from one of the definitions of strongly NP completeness. $\endgroup$ Jan 29 at 16:31
  • $\begingroup$ en.wikipedia.org/wiki/Turing_machine#Description: "Each cell contains a symbol from some finite alphabet." $\endgroup$
    – D.W.
    Jan 29 at 23:13

If there is just one symbol which can appear on the tape, then nothing about the tape can ever change. Thus, the tape is absolutely useless, and you are left with a finite bidirectional automaton.

However, the blank symbol $\bot$ is often treated as a special case. We could thus consider the situation where each cell on the tape can carry either $0$ or $\bot$, and where we can write a $0$ on a place previously containing a $\bot$, but we can never erase a $0$ and return that cell content to $\bot$. This is as close to unary as we can really get for a TM.

As long as we only consider decision problems, these machines still have the full power. Essentially, the idea is to insert a bunch of auxiliary bits between the bits containing the actual content, and then so simply copy everything to a fresh chunk of tape whenever we need to erase a bit, except for the bit to be erased.

Having a finite number of tape symbols greater than 1 doesn't make much a difference. So binary is just special here because its the smallest alphabet that easily works.

  • $\begingroup$ I think I lack some background data to fully understand your answer. I am just about to sleep but I have made a bookmark in my bookmarks bar and should read it much more focusedly tomorrow. I had trouble understanding "you are left with a finite bidirectional automaton" ; what does it mean? Please feel free to edit. $\endgroup$
    – Semo
    Jan 29 at 18:32
  • $\begingroup$ What is the "blank symbol" which is often treated as a special case? I can't copy it. I would like to read about it in Wikipedia. $\endgroup$
    – Semo
    Jan 30 at 4:07
  • $\begingroup$ @Semo In the wikipedia article, they use "b" for the blank symbol (in the formal definition subsection). Assuming you know usual finite automata, a bidirectional one would be one that doesn't have to read the input start-to-end, but that can go back (depending on the current state). Or, alternatively, it just what you get if you take away the ability to alter the tape from a TM. $\endgroup$
    – Arno
    Jan 30 at 10:32
  • $\begingroup$ Thank you so much Arno, if indeed we take away the ability to alter the tape, all we have is an infinite and symboless tape, is that correct? $\endgroup$
    – Semo
    Jan 30 at 14:13
  • $\begingroup$ Furthermore, trying to read the answer (which I find great) about the fourth time, I understand that the "simple" answer is that indeed TM is always binary as even in one symbol film there could either be a b, or a 0 and a 0 cannot be erased to be a b again, so "two states in one place" should always take part, otherwise it's not a TM. $\endgroup$
    – Semo
    Jan 30 at 19:01

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.