C.B.Price University of Worcester Revised Draft October 2012
The Discovery of the Computer Part II
Summary
As we have heard in the previous session, David Hilbert posed a fundamental question, as to whether it is possible to decide if any given theorem expressed in a logical system is true or false, without producing all the possible theorems of the system. This so-called “decision problem” was answered by Alan Turing, who showed that it is not possible to decide if any theorem is true or false. In doing this, he discovered the computer, and so defined our contemporary world.
We have seen various systems of logic from those of Leibnitz and Boole to the “MUI” and “pq” Post-production systems. Consideration of the latter led us to understand the need for a “decision procedure”, for example, to answer the question
In the MUI system, is the string MU a theorem?”
This question means that if we are given the axiom and production rules of the MUI system, can we decide if MU is a theorem of the system without running through a series of production steps which may not terminate? In other words, is there an algorithm which could solve the decision problem? If this algorithm could be found, it would reduce all human deductive reasoning to mechanical calculation.
In 1935, Turing, a student at Cambridge learned of Hilbert’s question. Following the work of Kurt Goedel mathematicians felt that the decision question could not be answered in the affirmative. Turing began to think about how to prove this. He succeeded and, as a side effect, discovered the universal computer.
Remember that solving a problem in logic involves a sequence of mechanical steps. Such a sequence of mechanical steps, each of which is unambiguous and which does not go on for ever is called an “algorithm”. Turing was of course aware of this abstract concept of an algorithm, but he decided to focus on the actual steps a human carried out when executing an algorithm, e.g multiplying 25 by 11. His analysis focused on the essential steps, removing irrelevant details such as what the human had for lunch. He saw that these steps were indeed mechanical (ie did not require any high level of thought), and so could be executed by a machine.
He then showed that no machine, carrying out those basic actions could decide whether any given theorem could be proved without calculation, and so he proved that there is no algorithm which exists which could decide if a theorem was true. He therefore answered Hilbert’s “decision question” in the negative. As a byproduct, he found a mathematical model of an all-purpose computing machine.
The Finite State Machine
To understand the power of the Turing Machine, we must put it into context, and this requires a small diversion to reflect upon the workings (and limitations) of “Finite State Machines”. Take a typical example, a soft drink dispenser. Let’s agree that a drink costs 30 crowns, and that in your pocket you have coins of denomination 10 and 20 crowns. The dispenser starts in a state of “no crowns inserted”. You put in a 10 crown coin, and the machine goes into a state of “10 crowns inserted”. Then you put in a 20 crown coin, and the machine goes into a state of “30 crowns inserted” and dispenses your drink. Of course, you may put in other combinations of coins, but the dispenser must ultimately come into the state “30 crowns inserted” and dispense your drink. The whole tree of possibilities is captured in the naive “state diagram” shown below:
Here each state is labeled with a symbol S1,S2,S3,… and the transitions between the states are shown as the events of depositing a coin of 10 or 20 crowns. Remember that each state “knows” how much money has been deposited. Double-circled states are the halting states where the FSM halts and dispenses a drink.
Another interesting FSM is the “bracket checker” which gets as inputs strings such as (a + b) * c or ( 3*(2+4) + 7). In these strings there are an equal number of left and right brackets. Here’s a FSM which can check brackets. Lets say we have the input string ( a ). We start in S0 and read the next symbol “(“, and so take the arrow to the right into S1. Then we read the symbol “a” and loop back into S1 since we don’t have a “(“ or a “)”.
No we read a “)” and we return to S0, where we have matched brackets. When we were in S1 we had one unmatched “(“ and in So we have none, that’s the meaning of the state number, so in S2 we’ll have 2 unmatched left brackets. Try this out for the strings “( ( )” which brings us back into S1 and “( ( ) )” which brings us back into S0. See how it works? Good. But let’s say we had the following string “( ( ( ) ) )”, which state do we end up in? In fact this FSM cannot handle this string since there are three (‘s and the machine can only handle two. Easy to fix, you say, we must just add another state S3 to the right, and if we needed to check 10 brackets, we would extend S0 up by 10 states. Correct, but what about if we do not know how many brackets we need to check, such as in a large piece of computer software. The FSM is useless in the general case even though it may work in specific cases, since the FSM needs to know the maximum number of brackets beforehand. As we shall see, the Turing Machine solves this problem, and is able to handle the general case.
Turing’s Analysis
Turing made an analysis of what computers were doing. But this was in the 1930’s where “computers” were people (usually women) who were performing calculations on paper. A typical calculation could be to find the result “31 x 9 = ?”. They would read numbers set out on a sheet of paper, pay attention to numbers and write intermediate results rather like we would do when making a multiplication like
31 x
9
------
------
By observing this process and analyzing what was going on, Turing came to realized that the two-dimensional sheet of paper could be replaced by a one-dimensional “tape” as shown Below. At each stage of the computation, the computer would look at her tape at one or more positions, read the symbols and decide what to do based on her “state of mind” (eg whether she was in an adding state of a multiplying state). For example in (a) she is looking at 1 and 9 and decides to multiply and write the result further along the tape. Then she moves her attention to one place on the left and then multiplies 3 by 9 and moves to the right to write the partial result onto the tape.
The final result of these operations is shown in (c). Then she moves her attention further along the tape (d) and adds the partial results of each multiplication by scanning her focus of attention along the tape to the right.
Turing made the following conclusions about the computer (a) She carries out a computation by reading and writing symbols on a tape, (b) She pays attention just to one square (looking at several squares simultaneously could be replaced by looking at each square in turn and remembering what has been seen). Her next action depends on the symbol she reads and her “state of mind”. Her next action will be to write a symbol on a square and then shift her attention to the square on the left or the square on the right.
Definition of the Turing Machine
The Turing Machine is like a Finite State Machine, but it contains a tape where input and output symbols are written. AS shown below, at any time, the machine is in a state, here Q1, and reads a symbol from the tape, here 2. Then it writes a symbol on the same square, here X, and then moves one place to the right and enters state Q2.
We can represent this in two ways, shown below. First as a state-transition diagram, rather like the diagrams we used for FSMs. Here Q1 is shown transiting to Q2, the arrow shows we have read a “2”, written an “X”, and have moved to the right “R”.
The second way of describing a Turing Machine is in tabular form. This is the method we used in class and in the workshop. Each line of the table shows the starting state, the symbol read, then the symbol written, the direction of movement of the read/write head, and the new state. The operation of this Turing Machine will be made clear in the following examples.
Examples of Turing Machine Programmes
(1) The Bracket Checker
This machine supersedes the FSM bracket checker, since it is able to handle an unknown number of matching brackets in the string. Here is the tabular description of the Turing Machine
Here’s a tape containing a well-formed string of brackets
The operation of the Turing machine when this tape is provided as input is shown in the trace below. This indicates the read/write head position, the movement of the head and symbols read and written At the right of each line in the list is indicated the current state as well as which line of the table (1-12) is being invoked. Symbols written are shown in bold face.
This trace is quite revealing how the TM bracket checker works. The machine clearly moves to the right, searches for the first “)”, and cancels it (writing an “X”) and then moves to the left and when it encounters a “(“ it cancels this too. Effectively it has found a matching “( )” pair and has cancelled them out. Then it moves to the right again and when it finds another “)” it cancels it, then returns to moving to the left to cancel out the corresponding “(“. Moving to the right is clearly associated with state A, and moving to the left is associated with state B. The third state C is entered when no more “)”’s are available and when there is one or none remaining left brackets. This state writes “1” if there are no remaining brackets, indicating a well-formed string, or 0 otherwise.
Here’s a tape containing an ill-formed string of brackets
(3) A Machine that Halts or Doesn’t
The Universal Turing Machine
Let us sketch out a Turing Machine in a different way (see below). The input tape t is presented to the Turing Machine T. This is our understanding of the Turing Machine which operates and analyzes the input tape and can change it by writing in its squares.
As we have seen, the Turing Machine reads each symbol on the tape and performs an action (write and move, enter a new state) according to the table description.
Turing considered the existence of another machine, the “Universal Turing Machine” which would accept and process a tape split into two parts:
The leftmost part consists of the tape t input into the original machine T, but the rightmost part of the tape is special. It contains the Goedel numbering of the machine T which we have called |G(T). The whole tape is a load of numbers, but whereas the left part is pure data (to be input into T) the right part is a numerical description of machine T. Turing saw that he could make an abstract Universal Machine that would read this whole tape, and would interpret the numerical description G(T) and use this to process the data t. In our contemporary language, we could think of the “Universal Machine” as our PC, the description G(T) as a (machine code programme) and t as the data input into the programme. Or even more concrete, The Universal Machine is an HP Laptop running Windows 7, G(T) is Microsoft Excel, and t is a spreadsheet of numbers and formulae.
The Halting Problem
Remember what Turing was about, to get a solution for Hilbert’s decision problem. We have suggested that an answer to this is a question of whether we can find an algorithm to solve this problem succeeds or does not. Well, let’s ponder. What does it mean for an “algorithm to succeed”? If it succeeds, then it provides an answer, in other words the process will halt, ie will stop in a reasonable time. Conversely, if it does not succeed then it will not halt and we could be waiting for an infinite number of reincarnations to find that it does not halt. This is a crucial problem.
Turing posed a simple question. “Can we make a Turing Machine D that will decide if another Turing Machine T will halt when it is fed with a data tape t?” Here’s how he answered that question.
Part 1. Let us assume that we can build a Turing Machine D that will decide if T will halt. The situation will look like this