Turing Machines and Computability

Computing Machines and Algorithms

An algorithm is a computational process that takes a problem instance and in a finite amount of time produces a solution. . . . It is hard to make the definition of algorithm more precise except by saying that a computational process is anything that can be done by a program for a computing machine, and in that case one must accept that a human being with paper and pencil is a kind of computing machine. (Floyd and Beigel, The Language of Machines, Computer Science Press, W.H. Freeman, 1994, p. 444.)

Computability and Decidability

Problems which are intended to be solved by a computational process may be stated in a variety of ways:

Decision Problems

A decision problem is stated as a question with a "yes" or "no" answer, such as:

• Is the number 23171 prime?
• Does 2005 January 1 fall on a Friday?
• Is the list of names in the file 'clients.txt' in sorted order?
• Does she love me?

If the problem is stated as a Boolean statement --- an assertion which is either true or false --- we call the statement a predicate.
If there is an effective procedure for answering the question or evaluating the assertion, we say that the problem is decidable.

Functions

Other problems require a unique but particular answer:

• What is the smallest prime factor of 23171?
• On which day of the week will the year 2005 begin?
• What ordering of the names in the file 'clients.txt' would represent ascending sorted order?
• Which persons from the following list of eligible bachelors love me?

This type of problem can be viewed as the evaluation of a function, since the answer is unique. It can also be viewed as a mapping of an input value to an output value. If we have a function that computes smallest prime factors, we give it 23171 as an input value and it yields 17 as an output value. Note that problems which we might think of as procedures or processes, such as sorting, can also be viewed as functions which map inputs to outputs --- a sorting program maps a given unsorted list of names to a unique sorted list of names.
A function is said to be computable if there is an effective procedure (an algorithm) for evaluating the function which, given any input or set of input values for which the function is defined, produces the correct result and halts in a finite amount of time. (If the function is undefined for some input values in its domain [i.e., it is a partial function rather than a total function], the procedure is not required to halt. For example, we can regard the problem of finding the smallest prime factor of a given natural number as computable even if it fails to halt if given 0 as an input, and assuming that we define the function to be 1 if the input number is prime or 1.)
A decision problem can be reformulated as a function by defining a function which returns 0 if the answer is 'no' or the predicate is false or 1 if the answer is 'yes' or the predicate is true.

Relations

Some problems may have multiple correct answers or no correct answers. (This is the general case which could be viewed as including the previous two categories.)

• Find a prime factor of 23171.
• What month in the year 2005 will have a Friday the 13th?
• What is a possible shuffled ordering of the following list of cards?
• Who loves me?

Mathematicians call such problems relations, because the answers are not unique.
A relation may be computable even if it doesn't produce a result, as would happen if we provided a prime number as the input to a prime-factor-finding procedure. Since we could reformulate a relation as a function by specifying a particular value to be returned if there is no answer to the problem and by defining the function to return a list of all the possible answers or a randomly selected answer if there are multiple correct answers to the problem, it suffices to talk about computable functions and to ignore the distinction between functions and relations for the purposes of determining computability.

Turing Machines and Computability

The Decision Problem

In 1936, Alan Turing published a paper called "On computable numbers, with an application to the Entscheidungsproblem [decision problem]", in which he addressed a previously unsolved mathematical problem posed by the German mathematician David Hilbert in 1928: Is there, in principal, any definite mechanical method or process by which all mathematical questions could be decided? (source)
To answer the question (in the negative), Turing proposed a simple abstract computing machine, modelled after a mathematician with a pencil, an eraser, and a stack of pieces of paper (Floyd and Beigel, p . 444). He asserted that any function is a computable function if it is computable by one of these abstract machines. He then investigated whether there were some mathematical problems which could not be solved by any such abstract machine. Such abstract computing machines are now called "Turing machines". One particular Turing machine, called a "Universal Turing Machine", served as the model for designing actual programmable computers.

The Turing Machine

A Turing machine (TM) consists of a control unit and a read/write head positioned over a tape of unlimited length which contains a finite string (sequence) of characters from some alphabet (designated set of possible characters). The tape is conceptually divided into squares or frames, each of which can hold precisely one character. The possible operations of a TM are:

• read the character in the square currently under the head
• write a character in the square under the head (overwriting the character that was there, if any)
• move the head one square to the right or left
• check if the tape head is at the left end of the tape

In most formulations, the tape is "one-way infinite", extending infinitely to the right. The head cannot move left from the left end of the tape; if it moves right beyond the end of the string on the tape to a previously unvisited square, this square is assumed to be blank (i.e., a blank is presumed to be a valid character in the designated alphabet). [The Turing machine simulator in the online materials accompanying the textbook does not behave this way --- you have to be sure to provide sufficient 'b' characters to represent blanks at the end of the input string.]
It is fairly easy to imagine how the read/write head operates on a tape -- we can imagine it as being similar to a tape recorder, or we can simulate its action using a pencil, an eraser, and a strip of paper. However, it is the contents of the control unit that really defines aTuring machine. While every Turing machine has a read/write head, a tape, and a control unit, it is the contents of the control unit that differentiates one Turing machine from another. Since we are familiar with modern computers, we might think of the contents of the control unit as the program that is loaded into the control unit's memory. The program determines what the Turing machine actually does.
Actually, it would be better to think of the program as being built in to the control unit, since Turing envisioned each Turing machine as being custom-built to execute a single algorithm (i.e., compute a single function.) The image of loading a program into a control unit would be more appropriately applied to the Universal Turing Machine, which we discuss below.
We can describe or define the "program" that is built in to a given Turing machine using a diagram or by listing the set of rules the control unit should follow. We can think of each rule as a single "instruction" in the Turing machine's program. In addition to the operations related to the read/write head listed above -- read a character, write a character, move left or right on the tape, and check to make sure we are not moving off the left end of the tape -- the control unit keeps track of what state it is currently in, and can change from one state to another if the current rule (instruction) says to do so. Typically, each state has a number of rules associated with it; different rules are used for each state. The control unit selects the rule that should be executed next depending on

• which state it is currently in and
• which character is read from the current square of the tape.

Most illustrations of the operation of Turing machines do very simple things on very simple input strings. For example, Lab 8.1 in the textbook illustrates the operation of TM1, a machine that copies a string of 0's and 1's (terminated by '!') to the blank portion of the tape, and TM2, which adds 1 to a positive integer represented in unary notation at the start of the tape. (See also a description of TM1 and TM2 using diagrams and explanatory text.) We typically use very simple Turing machines operating on simple input strings not because we can't define Turing machines to do complex tasks, but because it takes so many rules to do even simple things that we would quickly get confused trying to understand even a moderately complex Turing machine.
Why are descriptions of Turing machines so verbose? Because Turing purposely chose a very simple machine which is restricted to a few very simple operations in order to make it obvious that his proof of the answer to the decision problem was correct.

Why a Turing Machine?

Most actual computers do not use a tape for input, storage, and output --- they use random-access memory (RAM), stacks, and registers. So why do we use a Turing machine --- a tape machine --- as a model of computing?

1. It can be (i.e., has been) proved that a single one-way infinite tape "is computationally as powerful as any collection of known memory devices" (Floyd and Beigel, p. 92).
2. "Because Turing machines are very simple compared with computers in practical use, it is conceptually easier to prove impossibility results for Turing machines. These impossibility results apply as well to all known computers." (Ibid.)

One might also ask, "Aren't Turing machines slow?" Since the Turing machine is an abstract machine --- that is, it exists only as a mental concept, or as a diagram on paper --- its speed is both irrelevant and unknown. All we need to assume is that each operation of a Turing machine takes some non-zero amount of time to execute. This allows us to talk about Turing machines that never halt for some inputs. (If operations were assumed to be instantaneous, then even a process that required an infinite number of steps would finish right away, wouldn't it?)

The Church-Turing Thesis

Several other researchers tried to address the Decision Problem by other methods. Alonzo Church introduced recursive partial functions as a formalization of algorithmically computable functions. Emil Post proposed symbol manipulation systems for making logical deductions. When it was proven that all three models were equivalent (i.e., they defined the same class of functions, and agreed as to which of them are computable), Church recognized that "all formalizations of algorithms were destined to yield the same class of computable functions" (Denning, Dennis, and Qualitz, Machines, Languages, and Computation, Prentice-Hall, 1978, p. 477) and proposed what has come to be known as the Church-Turing thesis (given here as formulated by Floyd and Beigel, p. 444):

A Turing machine program can simulate any physically realizable computational process at all --- including that of the most powerful digital computers or a human being.

This is a thesis, not a theorem. It cannot be proven, because the term "computational process" (equivalently, "algorithm") is not formally defined. Turing proposed his abstract machines precisely for the purpose of formalizing the concept of algorithm.

The Universal Turing Machine

Turing also showed that it is possible (actually, fairly easy) to design a single Turing machine which can simulate the computations of any Turing machine, given an encoded description of the target TM and its initial configuration (the "input" string on its tape, the initial state, and the position of the head). Such a machine is called a Universal Turing Machine (UTM).
Physical programmable computers are effectively Universal Turing Machines which simulate the computations of any Turing machine (think, "algorithm" or special-purpose computer) by executing a program, which we can think of as a description of the computational process to be performed.
The existence of the UTM, together with the Church-Turing thesis, implies that "there is a certain minimal level of computational ability that is sufficient for any algorithmic computation" (Denning, Dennis, and Qualitz, p. 486).

Noncomputable Functions

The most startling result of Turing's 1936 paper was his assertion that there are well-defined problems that cannot be solved by any computational procedure. If these problems are formulated as functions, we call such functions noncomputable; if formulated as predicates, they are called undecidable. Using Turing's concept of the abstract machine, we would say that a function is noncomputable if there exists no Turing machine that could compute it.

Goedel Numbering

The proof that there are functions which are noncomputable uses a method of converting problems to numbers invented by Kurt Goedel.

Goedel numbering

A function that encodes each element of a set into a unique integer.

Just as we can encode any Turing machine in a description which can be submitted to a Universal Turing Machine for simulation, it is also possible to assign a "serial number" (a unique positive integer) to every possible Turing machine. Many different encoding methods are possible --- the textbook presents one method using binary strings. This implies that the set of all Turing machines is countable, that is, is in one-to-one correspondence with the integers.
However, the set of all functions f: N -> N (matchings of inputs to outputs over the natural numbers) is known to be uncountable. We must conclude that Turing machines are able to compute only a subset of the number-theoretic functions.

The Halting Problem

We might assume that those functions which are noncomputable mustn't be useful. However, Turing also provided a constructive proof for his thesis by showing that a particular function which would be very useful to computer scientists was noncomputable: the halting problem.

Given a Turing machine M and an initial tape T, does M halt when started on tape T?

The same problem can be stated in an alternative formulation which highlights its significance for computer scientists:

Given a program P and a string x, does P halt on input x?

Self-referential Paradoxes

Epimenides' Paradox:

This sentence is false.

The text below a picture of a pipe in Rene Magritte's The Air and the Song (1964):

Ceci n'est pas une pipe.

Bertand Russell's Barber Paradox:

The barber in a certain town had a sign on the wall saying, "I shave those men, and only those, who do not shave themselves."

The proof that the halting problem is noncomputable relies on the same device illustrated in the preceding paradoxes and used by Goedel to prove his Incompleteness Theorem: self-reference.
Suppose there is an algorithm H to solve the halting problem: given an encoding of a program P and an input string x, it returns 'true' if program P halts on input x, and 'false' otherwise. Use H as a subroutine to perform the conditional test in the following program H' (as formulated by Floyd and Beigel, p. 479):

input x, a string which encodes a program
if program x halts on input x then

loop forever
else

halt

Note that this program passes its input string to the subroutine H both as the encoding of a program (or, equivalently, a Turing machine) and as the input string for which we are to determine if program x halts. This means that H' halts on input x only if x doesn't halt on input x.
What happens if we give H' its own description as its input string?
Hoare and Allison re-state the conclusion this way (in "Incomputability", Computing Surveys 4, no. 3 [Sept. 1972]):

Any language containing conditionals and recursive function definitions which is powerful enough to program its own interpreter cannot be used to program its own 'terminates' function.

Other Noncomputable Functions

There are many problems related to programs which are undecidable --- so many, in fact, that H.G. Rice proved the following theorem (using a complicated definition of "nontrivial"):

Any nontrivial property of programs is undecidable.

There are also undecidable problems in other subject areas. Note that proving that a problem is noncomputable does not mean that a solution cannot be computed in some cases (i.e., for some inputs), but that it is impossible to construct a solution that works for any input.

Diophantine Equations

It is impossible to write a program to find a solution for Hilbert's Tenth Problem (Diophantine Equations), that is, polynomial equations over the integers such as

xy - 3x²z + 62xyz - 14 = 0

References

A biography of David Hilbert including a list of the 23 problems he posed in his lecture at the International Congress of Mathematicians in Paris in 1900.
The Mathematical Problems of David Hilbert

Links to resources on Turing machines