8.8 References for Chapter 8

The Turing machine is taken froui [8]. At about the same time there were several less machine-like proposals for characterizing what can be computed, including the work of Church [1], Kleene [5], and Post [7]. All these were preceded by the work of Godel [3], which in effect showed that there was no way for a computer to answer all mathematical questions.

The study of multitape Turing machines, especially the matter of how their running time compares with that of the one-tape model initiated with Hartmanis and Stearns [4]. The examination of multistack and counter machines comes from [6], although the construction given here is from [2].

to an ID with an accepting state. Although seemingly more powerful than the deterministic TM, the NTM is not able to recognize any language that is not RE.

4- Semi-infinite-Tape Turing Machines: We can restrict a TM to have a tape that is infinite only to the right, with no ceils to the left of the initicil head position. Such a TM can accept any RE language.

4- Multistack Machines: We can restrict the tapes of a multitape TM to behave like a stack. The input is on a separate tape, which is read once from left-to-right, mimicking the input mode for a finite automaton or PDA. A one-stack machine is really a DPDA, while a machine with two stacks can accept any RE language.

4- Counter Machines: We may further restrict the stacks of a nmltistack machine to have ordy one symbol other than a bottom-marker. Thus, each stack functions as a counter, allowing us to store a nonnegative integer, and to test whether the integer stored is 0, but nothing more. A machine with two counters is sufficient to accept any RE language.

♦ Simulating a Turing Machine by a real computer: It is possible, in principle, to simulate a TM by a real computer if we accept that there is a potentially infinite supply of a removable storage de\ice such as a disk, to simulate the nonblank portion of the TM tape. Since the physical resources to make disks are not infinite, this argument is questionable. However, since the limits on how much storage exists in the universe are unknown and undoubtedly vast, the assumption of an infinite resource, as in the TM tape, is realistic in practice and generally accepted.

4- Simulating a Computer by a Turing Machine: A TM can simulate the storage and control of a real computer by using one tape to store all the locations and their contents: registers, main memory, disks, and other storage devices. Thus, we can be confident that something not doable by a TM cannot be done by a real computer.

366 CHAPTER 8. INTRODUCTION TO TURING MACHINES

The approach in Section 8.1 of using hello, world as a surrogate for acceptance or halting by a Turing machine appeared in unpubhshed notes of S. Rudich.

1. A. Church, An undecidable problem in elementary number theory, American J. Math. 58 (1936), pp. 345-363.

2. P. C. Fischer, Turing machines with restricted memory access, Information and Control 9:4 (1966), pp. 364-379.

3. K. Godel, Uber formal unentscheidbare satze der Principia Mathematica und verwander systeme, Monatschefte fur Mathematik und Physik 38 (1931), pp. 173-198.

4. J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Transactions of the AMS 117 (1965), pp. 285-306.

5. S. C. Kleene, General recursive functions of natural numbers, Mathe-WAtische Annden 112 (1936), pp. 727-742.

6. M. L. Minsky, Recursive unsolvability of Posts problem of tag and other topics in the theory of Turing machines, Annals of Mathematics 74:3 (1961), pp. 437-455.

7. E. Post, Finite combinatory processes-formulation, J. Symbolic Logic 1 (1936), pp. 103-105.

8. A. M. Turing, On computable numbers with an application to the Ent-scheidungsproblem, Proc. London Math. Society 2:42 (1936), pp. 230-265. See also ibid. 2:43, pp, 544-546.

Chapter 9

Undecidability

This chapter begins by repeating, in the context of Turing machines, the argument of Section 8.1, which was a plausibihty argument for the existence of problems that could not be solved by computer. The problem with the latter proof was that we were forced to ignore the real limitations that every implementation of С (or any other programming language) has on any real computer. Yet these limitations, such as the size of the address space, are not fundamental hmits. Rather, as the years progress we expect computers will grow indefinitely in measures such as address-space size, main-memory size, and others.

By focusing on the Turing machine, where these limitations do not exist, we are better able to capture the essential idea of what some computing device will be capable of doing, if not today, then at some time in the future. In this chapter, we shall give a formal proof of the existence of a problem about Turing machines that no Turing machine can solve. Since we know from Section 8.6 that Turing machines can simulate real computers, even those without the limits that we know exist today, we shall have a rigorous argument that the following problem:

Does this Turing machine accept (the code for) itself as input?

cannot be solved by a computer, no matter how generously we relax those practical limits.

We then divide problems that can be solved by a Turing machine into two classes: those that have an algorithm (i.e., a Turing machine that halts whether or not it accepts its input), and those that are only solved by Turing machines that may run forever on inputs they do not accept. The latter form of acceptance is problematic, since no matter how long the TM runs, we cannot know whether the input is accepted or not. Thus, we shall concentrate on techniques for showing problems to be undecidable, i.e., to have no algorithm, regardless of whether or not they are accepted by a Turing machine that fails to halt on some inputs.

We prove undecidable the following problem: