4
$\begingroup$

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!

$\endgroup$
6
  • 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
  • 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
  • 1
    $\begingroup$ I suspect the point of the question isn't about binary, but that the cells in the Turing Machine can only be inhabited from a finite alphabet rather than holding an arbitrarily large natural number. At least by 1967 a limited cell description was known, since it is given in Roger's Theory of Recursive Functions. He attributes it to Davis 1958. If you research that you might find something earlier. $\endgroup$ – DanielV Jul 20 '17 at 4:01
6
$\begingroup$

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.

$\endgroup$

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.