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

Question

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?

Of course, it is obvious that you can represent any number using binary. But, first of all, Turing-machines can compute things about things other than numbers. Indeed, all that matters is that the Universal Turing-machine is able to represent, in binary, whatever symbol set the Turing-machine to be simulated is using, and a program, again in binary, that describes the state-transitions of that machine-to-be-simulated. Of course, since all of those things are enumerable, all representations of those things can still be done in binary, that is still fairly obvious.

But what is far less obvious to me, is that you can do all the computations on those represented objects still using only two symbols. For example, you'll need some way to indicate separations between the objects, and as those objects change (e.g. when the machine-to-be-simulated changes a symbol on the tape), you'll need to change the corresponding binary representation, and since they are of variable length, you'll need to constantly shift the location of those objects on the tape that the Universal machine is working with.

Indeed, to me the tricky part is to come up with some clever way to encode any kind of Turing-machine and input tape that the Universal machine will take in at its input, and to somehow simulate the behavior of that machine, keeping track of what state that machine is in and where it is on the tape, again, all with just two symbols. Yes, we now know it can all be done, and I successfully went through this exercise myself. However, I thought it was all rather less than obvious.

Of course, I am no Turing ... and so was it obvious to Turing that it could be done? Reading his paper, I don't think Turing really proves this .. or even considers this. In his paper, for example, he still uses special symbols (i.e. not 0 or 1) to, for example, indicate the left boundary of the simulated tape. But was it still so obvious to Turing that it didn't even deserve mentioning?

So, let me put it this way: is there a publication that can be considered the 'first' proof of the result that you can have a dully binary Universal Turing machine? I would be very interested in knowing what that is.

Thank you!

Answer 1

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.