# Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet?

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!

• 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? – Raphael Jul 19 '17 at 5:26
• @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? – Bram28 Jul 19 '17 at 13:51
• 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.) – Raphael Jul 19 '17 at 14:30
• 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. – David Richerby Jul 19 '17 at 19:36
• 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) – Raphael Jul 19 '17 at 21:26

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.