The title says it all, I think.

We know there are universal Turing-machines that only use a binary alphabet. But who proved this first?

Turing himself showed the existence of a universal Turing machine ... but did he also show that such a machine can exist using only a binary alphabet? Or was that someone else?

Or was it just 'obvious' to him and others that this would be the case, and hence no explicit 'first' proof or publication of this result exists?

But if there is a publication that can be considered the 'first' proof of this result, I would be very interested in knowing what that is.

Thank you!

  • 2
    $\begingroup$ Not sure if there's meat to this question. It seems obvious to me that you can simulate $k$-nary alphabets using binary, so any universal machine would qualify? $\endgroup$ – Raphael Jul 19 '17 at 5:26
  • $\begingroup$ @Raphael Sure, it's obvious now, but was it obvious then? Was it so obvious to Turing himself, for example, that he didn't even bother to mention it in his original 1936 paper? As far as the 'meat' to this question goes, I am asking a historical question: is there a 'first' publication of this result? $\endgroup$ – Bram28 Jul 19 '17 at 13:51
  • $\begingroup$ I don't know. However, number encodings are older than computability, so my guess is yes, it was obvious even then. (Note, though, that I posted a comment, not an answer.) $\endgroup$ – Raphael Jul 19 '17 at 14:30
  • 1
    $\begingroup$ I agree with @Raphael: the fact that you can simulate any alphabet with binary seems to me to be as obvious as the fact tht you can express any number in binary. I wouldn't expect anybody to bother mentioning the possibility of using a binary alphabet unless they had some reason to find that intrinsically interesting. Honestly, I don't think you need to give a citation for this: it's just an obvious fact that anyone who thought about the problem for a moment would derive for themself. $\endgroup$ – David Richerby Jul 19 '17 at 19:36
  • 1
    $\begingroup$ FWIW, non-trivial results in this direction are about universal TMs with less than k alphabet symbols and less than n states. That's a whole different deal, since the trivial result we have in mind blows up the state space quite a bit. (cc @DavidRicherby) $\endgroup$ – Raphael Jul 19 '17 at 21:26

A large part of what is known goes unpublished, when it is considered trivial. What counts as trivial is, of course, different in different times and for different communities. For instance, we do not consider particularly interesting about binary numbers that they are as expressive as decimals, but that the machines that operate on binary representations are simpler.

In his famous 1936 article, Turing is satisfied with the premise that the alphabet of the machine is finite, which leads me to believe that differences beyond that are considered trivial by him, for general purposes.

He discusses the difference between machines with infinite and finite sets of symbols, and reaches the conclusion that using an infinite set of symbols would, at some point, make it impossible to concretely differentiate them from each other (which could be another way of illustrating the fact that real numbers can't be listed). He then states that the effect of this restriction is not very serious, because you can, at least to some extent, conveniently represent bigger alphabets by groups of symbols of smaller ones, considering that any effective computation can only use, in practice, what amounts to a finite number of symbols.

I suggest that you try to imagine how to simulate an $n$-symbol TM (I would start with $n=8$) on a two-symbol one. It is a good exercise.

| cite | improve this answer | |

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.