13 Computability

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 instant 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 design for a machine.

A Turing machine is coupled to the tape through a read/write mechanism called the head or read/write head. The head is always positioned over one of the tape cells and may be moved (left or right) one tape position at a time.

13.1.1 Diagram of a Turing Machine

A Turing machine consists 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 (called the starting location) and is assumed to be in an initial state (called the 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.

e) Enter the new state.

13.2 A J Model of a Turing Machine

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


tape =: 1 ; 1 ; 1 ; 1 ; 0 ; 0

describes a tape which has 6 positions.

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


   open 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_odd 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 as follows.


   turing even_or_odd ; 0 ; tape ; 0
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. We can use a traced version of the Turing machine model by entering the following:


   traced_turing even_or_odd ; 0 ; tape ; 0
Entering, input =
+-+-------------+-+
|0|+-+-+-+-+-+-+|0|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|1|+-+-+-+-+-+-+|1|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|0|+-+-+-+-+-+-+|2|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|1|+-+-+-+-+-+-+|3|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|0|+-+-+-+-+-+-+|4|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|2|+-+-+-+-+-+-+|5|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+----+----------------+-+
|halt|+-+-+-+-+-+----+|4|
|    ||1|1|1|1|0|even|| |
|    |+-+-+-+-+-+----+| |
+----+----------------+-+
halt, position=
4
tape=
+-+-+-+-+-+----+
|1|1|1|1|0|even|
+-+-+-+-+-+----+

The traced_turing program does not print the machine contents before each machine cycle, since that input never varies.

If we use a starting position of 1, then we have:


   traced_turing even_or_odd ; 0 ; tape ; 1
Entering, input =
+-+-------------+-+
|0|+-+-+-+-+-+-+|1|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|1|+-+-+-+-+-+-+|2|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|0|+-+-+-+-+-+-+|3|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|1|+-+-+-+-+-+-+|4|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+-+-------------+-+
|3|+-+-+-+-+-+-+|5|
| ||1|1|1|1|0|0|| |
| |+-+-+-+-+-+-+| |
+-+-------------+-+
Entering, input =
+----+---------------+-+
|halt|+-+-+-+-+-+---+|4|
|    ||1|1|1|1|0|odd|| |
|    |+-+-+-+-+-+---+| |
+----+---------------+-+
halt, position=
4
tape=
+-+-+-+-+-+---+
|1|1|1|1|0|odd|
+-+-+-+-+-+---+

To understand how the even_or_odd machine works, recall its definition.


   open 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 state alternate back and forth between states 0 and 1 as it scans right over the tape.

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.


read_symbol =: monad define
('tape' ; 'position') =. y.
if. (position < 0) or (position >: tally tape)
  do. error 'invalid tape position' , format position
  else. open position from tape
end.
)

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.


lookup_state_symbol =: monad define
('state' ; 'symbol' ; 'machine') =. y.
if. nullp machine
    do. error 'symbol, ' , (format symbol) , ' or state, ' , (format state) , ' not found'
  elseif. (state match head head machine) and symbol match head rest head machine
    do. head machine
  elseif. 1
    do. lookup_state_symbol state ; symbol ; box rest machine
end.
)

13.2.4 write_new_symbol

write_new_symbol writes a new symbol to the current tape position.


write_new_symbol =: monad define
('tape' ; 'position' ; 'new_symbol') =. y.
(box new_symbol) position amend tape
)

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.


new_position =: monad define
('i' ; 'move') =. y.
if. 'l' match move
    do. i - 1
  elseif. 'r' match move
    do. i + 1
  elseif. 1
    do. error 'invalid move ' , format move
end.
)

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.


turing =: monad define
('machine' ; 'state' ; 'tape' ; 'position') =. y.
if. 'halt' match state
  do. 'halt, position=' , (format position) , 'tape=' , format  tape
  else. symbol =. read_symbol tape ; position
        five_tuple =. lookup_state_symbol state ; symbol ; box machine
    turing machine ; (> 2 from five_tuple) ; (write_new_symbol tape ; position ; > 3 from five_tuple) ; new_position position ; 4 fro
m five_tuple
end.
)

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 J machine. This means that J machines are at least as powerful as Turing machines. Are there algorithms which can be programmed on a J machine but not on a Turing machine? If the answer to this question is no, then we may conclude that J machines are no more powerful than Turing machines.

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

Our J 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 J 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 J 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 in advance, 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, but 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 J 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 J 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 J programs with the numbers 0, 1, 2, ... , there must be functions for which there are no J programs which compute their values. In Section 13.3, we argued that J machines were no more powerful than Turing machines. Hence it follows that there must be functions whose values are not computable by any Turing (or J) machine. If we define a function to be computable to mean that there is a J 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 J programs we may write are programs which use the source text of J 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:


mystery =: monad define
if. 0 = 2 residue y.
  do. y. =. y. % 2
    if. y. > 1
      do. y. , mystery y.
      else. 1
    end.
  else. y. =. 1 + 3 * y.
    if. y. > 1
      do. y. , mystery y.
      else. 1
    end.
end.
)

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
   tally 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 J 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 J program p and data d and produces 1if the program halts or 0 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 J program (or Turing machine) such that:


halt =: monad define
('program' ; 'data') =. y.
if. ... body of the halt program ...
  do. 1
  else. 0
end.
)

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 the function:


selfhalt =: monad define 'halt y. ; y.'

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


contrary =: monad define
f =. monad define 'f y.'
if. selfhalt y.
  do. f y.
  else. y.
end.
)

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 ==> 1, then contrary will start an infinite recursion loop by applying f to its input. But this is a contradiction since contrary cannot both halt and not halt when applied to itself.

2. If selfhalt contrary ==> 0, then the else. clause of the if. expression, will be executed and return its value (i.e., halt). 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.