13 Computability ( Terminal Session on this Machine )

In Chapter 10 we learned about untractable computations. Such computations are not feasable, even on the fastest computers we can imagine, when the size of the problem is large. There remains, however, the question about whether, given a computer which is arbitrarily faster than any existingcomputer, there are problems which are not solvable on this computer. In this chapter we explore some theoretical ideas which provide a basis for deciding whether there are functions which cannot be computed using machines.

Some of the questions we consider are:

Can algorithms be found which solve all problems?

If a problem has an algorithm, can we be sure there will be feasable solutions to the problem?

Are some problems more difficult than others? Is there a way to classify the difficulty of problems?

When analyzing the details of an algorithm, does it make any difference what kind of computer the algorithm runs on? What machine capabilities should be assumed?

If the order of an algorithm is known for one computer, what can be said of the order of an algorithm when running on another machine?

Alan Turing provided answers to some of these questions through a very simple design for a machine.

13.1 Turing Machines

The British mathematician Alan Turing studied the problem of finding a minimal structure for a machine which was sufficient to compute most of the functions in mathematics. This work was done in the middle 1930's [Tur36] before the existance of electronic computers as we know them today.

A Turing machine is a simple device which is in one of a finite collection of states at any one point in time and which has an external memory system which is a list of cells, called the tape. The tape is considered to be as long as needed in either direction, but at any one instant in time, only a finite number of tape locations are in use. The fact that the tape can be as large as needed gives the Turing machine its considerable power. The model Turing machine which we construct below, of course, does not have a tape of infinite size. However, the model Turing machine does exihibit all of the important facits of this kind of computation.

A Turing machine is coupled to the tape through a read/write mechanism called the head or read/write head. The head is positioned over one of the tape cells.

13.1.1 Diagram of a Turing Machine

A Turing machine is a collection of 3 items.

1. state

The Turing machine state is a non-negative integer. There is a special state, called halt, which is used to stop the execution of the machine.

2. a collection of 5-tuples

Each 5-tuple consists of the items

a) current state

b) current symbol

c) new state

d) new symbol

e) move (either l or r, i.e., move left or move right)

3. a tape memory

The tape memory is a collection of symbols which are accessed sequentially as the Turing machine read-write head is positioned over locations on the tape.

Initially, a Turing machine's read-write head is positioned over a particular tape location and is assumed to be in an initial state.

A Turing machine performs machine cycles continuously, one after another, until it achievs a halt state. Each machine cycle consists of the following steps:

13.1.2 Turing Machine Cycle

a) Read current symbol from the current tape location.

b) Lookup that symbol amongst the 5-tuples which match the current machine state to determine a new symbol to be written to the current tape position and a new state and a left or right move.

c) Write the new symbol to the current tape position.

d) Move the read-write head left or right to an adjacent tape location.

13.2 A Scheme Model of Turing Machines

We will use a Scheme list to model the tape of a Turing machine. For example,


(define tape '(1 1 1 1 0 0))

describes a tape which has 6 positions.

We use a Scheme list of 5 element lists to model a Turing machine's collection of 5-tuples. For example,


(define even-or-odd
  '((0 1 1 1 r)
    (0 0 2 0 r)

    (1 1 0 1 r)
    (1 0 3 0 r)

    (2 0 halt even l)
    (2 1 halt even l)

    (3 0 halt odd l)
    (3 1 halt odd l)))

The even-or-odd machine is designed to determine whether the number of 1's in a consecutive string of 1's is even or odd. The starting state for even-or-add is 0 and the starting tape position is assumed to be the left most 1 of the string to be scanned. This machine also assumes that there is a 0 after the last 1 in the string and that there is at least one more tape position to the right of the 0 to hold the halt symbol.

To see how the even-or-odd machine operates we envoke the Turing machine model after having turned on tracing for the simulator.


(trace 'turing)
(turing even-or-odd 0 tape 0) ==>
"CALLED" turing ((...) ...) 0 (1 1 1 1 0 0) 0
 "CALLED" turing ((...) ...) 1 (1 1 1 1 0 0) 1
  "CALLED" turing ((...) ...) 0 (1 1 1 1 0 0) 2
   "CALLED" turing ((...) ...) 1 (1 1 1 1 0 0) 3
    "CALLED" turing ((...) ...) 0 (1 1 1 1 0 0) 4
     "CALLED" turing ((...) ...) 2 (1 1 1 1 0 0) 5
      "CALLED" turing ((...) ...) halt (1 1 1 1 0 even) 4

ERROR: halt, position  4 " tape " (1 1 1 1 0 even)

Since there were and even number of 1's the even-or-odd Turing machine writes the symbol even on tape position just after the terminating 0. If we use a starting position of 1, then we have:


(turing even-or-odd 0 tape 1) ==>
   "CALLED" turing ((...) ...) 0 (1 1 1 1 0 0) 1
    "CALLED" turing ((...) ...) 1 (1 1 1 1 0 0) 2
     "CALLED" turing ((...) ...) 0 (1 1 1 1 0 0) 3
      "CALLED" turing ((...) ...) 1 (1 1 1 1 0 0) 4
       "CALLED" turing ((...) ...) 3 (1 1 1 1 0 0) 5
        "CALLED" turing ((...) ...) halt (1 1 1 1 0 odd) 4

ERROR: halt, position  4 " tape " (1 1 1 1 0 odd)

To understand how the even-or-odd machine works, recall its definition.


(define even-or-odd
  '((0 1 1 1 r)
    (0 0 2 0 r)

    (1 1 0 1 r)
    (1 0 3 0 r)

    (2 0 halt even l)
    (2 1 halt even l)

    (3 0 halt odd l)
    (3 1 halt odd l)))

The first 5-tuple, (0 1 1 1 r), is read as follows: in state 0, if the symbol in the current tape location is 1, change the state to 1, write a 1 back to that tape position and move to the tape position on the right. The third 5-tuple, (1 1 0 1 r), is interpreted as: in state 1, if a 1 is read from the current tape location, change to state 0, write a one back to the current location and move to the tape location on the right. When we look at the trace output of the Turing machine simulator, we can see the even-or-odd machine alternate back and forth between states 0 and 1.

If the machine is in state 0 and a 0 is read from the tape, the second 5-tuple, (0 0 2 0 r), is read as; in state 0 if a 0 is read, enter state 2, write a 0 back to the tape and move right. This state handles finding the 0 at the end of the string of 1's after having scanned over an even number of 1's. Notice that when the machine is in state 2 and finds either a 0 or 1 on the tape, the halt state is entered, the symbol even is written to the tape and the head is moved left. The machine then halts.

13.2.1 Exercise

Explain how the even-or-odd machine scans an odd number of 1's, producing a result of the symbol odd being written to the tape.

Next we discuss the component parts of the Turing machine simulator.

13.2.2 read-symbol

read-symbol reads the symbol on the current tape location. It performs an error check to insure that the tape location is valid. Notice that read-symbol assumes the tape has a fixed finite length. As a result, our model does not accurately reflect a real Turing machine. However it would be easy to append a new tape location on the left whenever the position value is -1 or append a new tape location on the right when the position value is equal to the length of the tape.


(define read-symbol
  (lambda (tape position)
	  (if (or
	       (< position 0)
	       (>= position (length tape)))
	      (error "invalid tape position " position)
	      (list-ref tape position))))

13.2.3 lookup-state-symbol

lookup-state-symbol finds a 5-tuple in a Turing machine which matches a given state and symbol. An error condition is generated if no match is found. Such an error occurs when a machine enters a state for which there is no definition or searches for a tape symbol which was not defined in the machine.


(define lookup-state-symbol
  (lambda (state symbol machine)
	  (if (null? machine)
	      (error "symbol or state not found,
                     symbol=" symbol " state=" state)
	      (if (and
		   (eq? state (caar machine))
		   (eq? symbol (cadar machine)))
		  (car machine)
		  (lookup-state-symbol state symbol (cdr machine))))))

13.2.4 write-new-symbol

write-new-symbol writes a new symbol to the current tape position. Since the tape is represented as a Scheme list, we use a function from Chapter 2., list-subst, which builds a new list after changing a single element.


(define write-new-symbol
  (lambda (tape position new-symbol)
	  (list-subst tape position new-symbol)))

(define list-subst
  (lambda (ls i v)
	  (define subst-helper
		  (lambda (cnt new-value lst result)
			  (if (= cnt 0)
			      (append
                      (append result (list new-value))
                      (cdr lst))
			      (subst-helper (- cnt 1)
					    new-value
					    (cdr lst)
					    (append result (list (car lst)))))))
	  (subst-helper i v ls '())))

13.2.5 new-position

new-position computes the new tape location from the current location given a move of l or r which is determined from the 5-tuple which matches the current state and current symbol.


(define new-position
  (lambda (i move)
	  (case move
		((l) (- i 1))
		((r) (+ i 1))
		(else (error "invalid move " move)))))

new-position also checks for invalid moves, i.e. moves which are not l or r.

13.2.6 turing

turing performs Turing machine sycles, one after another, until the Turning machine enters the halt state. A Turing machine, an initial state, a tape and an initial tape position are required arguments.


(define turing
  (lambda (machine state tape position)
	  (if (eq? 'halt state)
	      (error "halt, position " position " tape " tape)
	      (let* ((symbol (read-symbol tape position))
		     (5-tuple (lookup-state-symbol state symbol machine)))
			(turing
			 machine
			 (list-ref 5-tuple 2)
			 (write-new-symbol tape position (list-ref 5-tuple 3))
			 (new-position position (list-ref 5-tuple 4)))))))

13.3 Turing Machines and Other Computer Designs

A Turing machine has a very simple design. Modern computers are based on rather complex designs in comparison to a Turing machine. We have constructed a Turing machine using a Scheme machine. This means that Scheme machines are at least as powerful as Turing machines. Are there algorithms which can be programmed on a Scheme machine but not on a Turing machine? If the answer to this question is no, then we may conclude that Scheme machines are no more powerful than Turing machines.

If an algorithm can be implemented on a Turing Machine and another computer, such as a Scheme machine, how do the orders of these two algorithm implementations compare?

Our Scheme based Turing machine used a tape which had tape positions 0, 1, 2, .... and extended as far to the right as needed. Turing's original design for the machine used a tape which extended as far to the left as needed having positions ..., -2, -1, 0, 1, 2, .... . This design is equivalent to our Scheme based design since we can represent Turing's tape as one extending only to the right by the following ordering of tape positions: 0, -1, 1, -2, 2, ... . Turing machine tapes are infinite in size while our Scheme machines always have finite amounts of memory. This would seem to be an area where the Turing machine must be more powerful. However, Turing machines always operate on a finite sequence of input symbols and are limited to moving one symbol at a time. After a finite number of processing steps, a Turing machine could have written at most a finite number of symbols. If an upper bound on the number of operations required by an algorithm is known, then it is possible to replace the infinitely large tape of a Turing machine with a sufficiently large finite tape. Using arguments similar to these, it is possible to establish (proof is beyond the scope of this course) that Turing machines have the same processing power as modern electronic computers. The efficiency of Turing machines may be less than a modern electronic computer on a given problem, the orders of the two algorithms can be shown to be the same.

13.4 Class P Problems and Intractable Problems

In Chapter 10 we defined tractable algorithms as those having execution times of whose order was a polynomial in n, the size of the problem. We call problems Class P if there exist at least one tractable algorithm which solves the problem. We saw algorithms having exponential order (recursive Fibonacci algorithm and Tower of Hanoi). We found an algorithm having linear (order n) execution time for the Fibonacci problem, however, it may not be possible to find tractable algorithms for each problem known to have algorithms whose orders are greater than any polynomial in n. Such problems are called intractable problems.

13.5 Problems With No Solutions

If we consider all the possible different functions which may be defined, among these are the functions whose values are not rational numbers. There are at least as many of these functions as there are non-rational numbers. There are infinitely many of these functions and it is a fact (proof of which is beyond the scope of this course) that these functions may not be put into 1 to 1 correspondence (paired with) the numbers 0, 1, 2, ... . On the other hand, if we consider all of the different Scheme programs we can construct (each program is constructed by choosing finitely many symbols from a finite symbol set; the ASCII character set), each of these may be paired with the numbers 0, 1, 2, ... . To see how to do this consider ordering each of the valid program by the smallest size, next smallest size, etc. Amongst all of the Scheme programs of a given size (there are only finitely many of these because each is choosen from a symbol set of finite size) one can choose an arbitrary ordering of these programs and then move on to the programs of the next larger size. Since we can establish a 1 to 1 correspondence between all of the Scheme programs with the numbers 0, 1, 2, ... , there must be functions for which there are no Scheme programs which compute their values. In Section 13.3, we argued that Scheme machines were no more powerful than Turing machines. Hence it follows that there must be functions whose values are not computable by any Turing machine. If we define a function to be computable to mean that there is a Scheme program (or Turing machine) which computes its value, then we have established that there exist functions which are not computable or problems which do not have solutions. In the next section we give an example of such a problem.

13.5.1 The Halting Problem

Among all of the possible Scheme programs we may write are programs which use the source text of Scheme programs and their data as input. Consider the task of writing a program which would attempt to determine, after reading and analyzing the input program and data, whether or not that program would halt (terminate in a finite amount of time) given those data as input. Programs which do not use recursion or iteration are fairly easy to analyze, but programs such as:


(define mystery
  (lambda (x)
    (if (even? x)
      (let ((y (/ x 2)))
        (if (> y 1)
            (cons y (mystery y))
            '(1)))
      (let ((y (+ 1 (* x 3))))
        (if (> y 1)
            (cons y (mystery y))
            '(1))))))

are much more complex. The mystery function seems to build a list of integer values ending, finally in 1. However, no one has yet proved that this function always produces a list of finite length. For example,


> (mystery 17) ==>
(52 26 13 40 20 10 5 16 8 4 2 1)
> (length (mystery 1000000))
152

13.5.2 The Halting Problem is not Computable

To establish the non-computability of the halting problem requires proof that there is no Scheme program (or Turing Machine) which can determine whether or not a program will halt with its solution in a finite amount of time. The following proof uses the technique of proof by contradiction. Such proofs assume the desired result is false (in this case we will be assuming the existance of a program named halt which has arguments of a Scheme program p and data d and produces #t if the program halts or #f if the program does not halt) and show that this assumption leads to a contradiction. Note that proof by contradiction does not give any details about a constructive approach for the proof, but rather, just establishes the truth of the theorem being proved. Not all mathematicians accept proofs by contradiction.

13.5.3 Halting Problem Proof

Assume the Halting problem is computable. Then there is a Scheme program (or Turing machine) such that:


(define halt
  (lambda (program data)
    (if ... body of halt program ...
      #t
      #f)))

We do not need to know the details of the body of the halt program. All we need to know is that halt successfully does its job of determining whether or not program halts when applied to data.

We next define a function:


(define selfhalt
  (lambda (program)
    (halt program program)))

selfhalt uses halt to see whether or not a program halts when its data is the program itself. Next we define a function:


(define contrary
  (lambda (program)
    (if (selfhalt program)
      (letrec ((f (lambda () (f))))
        (f)))))

Now, consider what happens if we attempt to evaluate:


(contrary contrary)

This means that (selfhalt contrary) must be evaluated. There are two cases to consider.

1. If (selfhalt contrary) ==> #t, then contrary will start an infinite recursion loop by calling f. But this is a contradiction since contrary cannot both halt and not halt when applied to itself.

2. If (selfhalt contrary) ==> #f, then the if expression, having no alternate clause, will complete (halt) producing some unspecified value. But this is also a contradiction since this is the case where contrary does not halt on itself.

We have shown that both cases lead to a contradiction, so the original assumption, that the halting problem is computable, must be false. From this it must follow that the halting problem is not computable.

13.6 Bibliography

[Aho92] Foundations of Computer Science, Aho, Alfred and Ullman, Jeffrey, Computer Science Press, New York, 1992.

[Min67] Computation: Finite and Infinite Machines, Minsky, Marvin, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1967.

[Tur36] "On Computable Numbers with an Application to the Entscheidungsproblem", Alan Turing, Proc. London Math. Soc., Ser. 2-42, pp. 230-265.