1
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ If the answer to this question is too obvious, any hint would be welcome why. (Or any hint why this question disqualifies?) $\endgroup$ – Hans-Peter Stricker Aug 26 '14 at 18:07
  • $\begingroup$ Is it "un-mathematical thinking" to think about the reasons why a condition in a definition was chosen? Maybe it's "meta-mathematical thinking", but it's "mathematical" nevertheless, isn't it? Should I ask the question at meta.mathoverflow.net? $\endgroup$ – Hans-Peter Stricker Aug 26 '14 at 18:24
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ One might note that the proposed machine is Turing-complete using any computable prefix-free encoding of the natural numbers. $\endgroup$ – Sridhar Ramesh Aug 26 '14 at 19:53
  • $\begingroup$ Yes. For example, one could use unary input, which amounts in this case to imposing the Hopcroft/Ulman requirement. $\endgroup$ – Joel David Hamkins Aug 26 '14 at 19:55
  • 1
    $\begingroup$ Heh, good point. Though we might also consider more sophisticated prefix-free encodings, the simplest is to reserve an "Ok, we're done" character, and that's basically the role the blank symbol plays. $\endgroup$ – Sridhar Ramesh Aug 26 '14 at 20:01
  • $\begingroup$ @Joel: Thank you very much! (Now, that I know and understand your answer, I see that my question was not really "research level". Do you find it inappropriate for MO, too?) $\endgroup$ – Hans-Peter Stricker Aug 26 '14 at 20:02
  • 1
    $\begingroup$ Of course one can still expect to compute some things, as you've indicated. But your machines are not suitable for a full-fledged theory of computability, since they are not Turing complete. We could also handicap other kinds of Turing machines in various ways, to prevent them from being Turing complete, such as by insisting they run in polynomial time. Such a polytime handicap offers a computational model of an extremely robust and important class of decidability problems. Your model similarly handles some class of decidability problems, but I'm not sure how robust it is. $\endgroup$ – Joel David Hamkins Aug 26 '14 at 21:07
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah, nice encoding scheme! $\endgroup$ – Per Alexandersson Aug 26 '14 at 20:18
  • $\begingroup$ You seem to imply that one does not really need to require a blank symbol? So what is your specific answer? "In fact one does not need to require a blank symbol because there are encoding schemes that allow to neglect them?" How can this meta-mathematical statement be made totally precise? $\endgroup$ – Hans-Peter Stricker Aug 26 '14 at 20:24
  • $\begingroup$ It depends what you exactly need. Take Joel's example. For each number n, let ##n be the encoding I described above. (For example, ##100 = 11 00 00 10...) Let #n be the encoding you described (so #100 = 00100…). There is a Turning machine, which for all n, reads in the tape ##n, halts, and returns 1 if there are at most three 1s in n and 0 otherwise. The same is also true for every Turing computable function. However, as Joel said, you cannot ask for a Turning machine which reads in #n and returns 1 if there are at most three 1s in n and 0 otherwise. $\endgroup$ – Jason Rute Aug 26 '14 at 23:43

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.