Rationale behind an requirement on Turing machines

Question

Hopcroft and Ullman's definition of a Turing machine seems to be standard. This definition defines a Turing machine to be a 7-tupel $T = \langle Q,\Gamma,b,\Sigma,\delta,q_0,F \rangle$ obeying some requirements among which is:

The input alphabet $\Sigma$ is a subset of $\Gamma \setminus \lbrace b \rbrace$.

I.e. the input alphabet $\Sigma$ must not contain the blank symbol $b\in \Gamma$ which is the only symbol of the tape alphabet $\Gamma$ allowed to occur on the tape infinitely often at any step during the computation.

What does this requirement mean?

I assume that it is to guarantee that we can identify the (end of the) input. Consider $\Gamma = \{0,1\}$ and $b = 0$. An initial configuration of the tape is any function $f:\mathbb{Z} \rightarrow \{0,1\}$ with

• $f(k) = 1$ only for finitely many $k \geq 0$
• $f(k) = 0$ for all $k < 0$

Since the input may not contain any $0$s the only inputs are sequences of $1$s, starting at $k=0$. On the initial tape these sequences are followed by $0$ (thus marking the end of the input), followed by any sequence of $0$s and (finitely many) $1$s.

Thus according to this definition there are no Turing machines with tape alphabet $\Gamma = \{0,1\}$ that can handle numbers in binary representation. But seemingly there are such Turing machines. Consider for example the machine $T_{bin-double}$ that takes an arbitrary number $n$ in binary representation, moves the head to the left (where there is a $0$) and stops. When we start reading the output from the head position to the right the output is simply $n \cdot 2$ in binary representation.

(Compare $T_{bin-double}$ with the machine $T_{un-succ}$ that takes an arbitrary number $n$ in unary representation, moves the head to the left, writes a $1$ and stops. When we again start reading the output from the head position to the right the output is simply $n + 1$ in unary representation.)

Notice that both machines don't look for the end of the input: they operate only at the start of the input.

So, what is the true rationale behind the requirement that the input alphabet must not contain the blank symbol?

(Maybe it's interesting to notice that in the Wikipedia article no explicit use is made of $\Sigma$ further on?)

Answer 1

Your proposed treatment of having machines use binary input with the alphabet $\{0,1\}$, where $0$ counts as a blank symbol (so that the input is padded with infinitely many additional $0$s, is not Turing complete, since there will be sets of natural numbers that are decidable by ordinary Turing machines (including those satisfying the Hopcroft/Ulman requirement), but not by your modified machines. For example, the set of natural numbers having at most three $1$s in their binary representation is decidable by any of the ordinary accounts of Turing machine, but are not decidable by your machines. To see this, fix one of your machines, and let it operate on the all-$0$ string. Your machine must accept, since this is the representation of the number $0$, which is in the set. But the machine must have accepted at some finite stage, and we may now change the input beyond any of the cells that the machine had inspected during its computation by adding four $1$s very far out. The new input will lead to exactly the same computation by your machine, since those $1$ cells are never inspected, and so it will be accepted, but it should not be accepted, since we have four $1$s in the new input. Thus, this set is not decidable by your version of the machines and so your computational model is not Turing complete.

Answer 2

It is important to realize that a Turing machine---and even more so, a specific implementation of a Turing machine---is just one of many models of computation. The earliest models of computation, for example Turing's, were designed to take finite inputs (citation needed). This is sufficient to talk about computable functions from the natural numbers to the natural numbers. In this particular model, it seems obvious that "blank" means blank, and it is how the machine knows it has read all of the finite input. The idea is that the tape contains 0s and 1s on some, but not all cells.

Now, of course, you could create a different method to read in data that doesn't require a blank symbol. One trick is that the symbols 0, 1, and b can be encoded as 00, 11, and 10. Then the string, say, 010, can be encoded as 00 11 00 10 10 10… (spaces added for clarity). This is a different model of input, but one can design a machine in which this works.

There are also variations of Turing machines that take infinite inputs. This is a good model of computation for functions which take in infinite objects and return infinite objects. (Such machines don't halt. They just read in data, output data, read in more data, output more data, etc.) However, it should be noted that such a machine needs to make decisions on what to output before it has read all the (infinite) input. For example, the machine would behave (at least for a while) the same on the string 0000… and on the string 0000…000010000... where the location of the first 1 is a really big number.