Turing Machine

A Turing Machine (TM) is a mathematically idealised machine having:

• A finite and discrete set of possible internal machine states

• A read/write head

• An infinite storage tape divided into discrete cells inside each of which a single character is written (usually 0 or 1)
  • The tape serves as input, as storage space for data and intermediate results and as output medium.

  • All three of these are therefore potentially infinite i.e. there is no limit on the size of numbers involved in the computation.

  • But any particular calculation involves only a finite number of marks on the tape.

• The tape (or head) moves forward or backwards one cell at a time.

• A ``machine table'' i.e. a program of instructions
  • Condition (initial state + input)

  • Action (one of 4 operations - replace 0 by 1 or 1 by 0 or leave either as is, then shift left or right and go to next state)

    If Initial state __ and reading __ then print __, move L/R and go into state __

Example of TM: UN+1 (see Penrose (1989) or Luger (1994))

A TM is a deterministic system: initial state + input gives an output with probability 1 for TM; between 0&1 for a probabilistic automaton.

Universal Turing Machine: Each instruction of an arbitrary Turing machine can be coded into a binary numeral. The TM can thus be represented by a long numeral which is then used as the initial input of another TM. This UTM now acts on the remainder of the input just like the original TM would have done. How is this done?

• Systematic way of numbering TMs - 1#1, 2#2 ...

• Suppose the nth TM (3#3) acting on the number m produces output p

• Construct the UTM (whose tape consists of n, a separator and m) such that it's own list of instructions enable it to read an entry in n (the list of instructions for 3#3) and act with it on the number m. Thus U(n,m) produces the same output on a pair of numbers (n,m) as 3#3 produces when acting on m i.e., U when first fed with n, imitates the nth Turing machine.

• U is itself a TM: 4#4, where the smallest u is of the order of 5#5.

UTM thus takes the coded version of other Turing machines as input and then emulates their behaviour.

Turing's paper was a response to Hilbert's 10th problem: Is there an algorithm for solution of a given class of mathematical problems?

Algorithm = mechanical procedure = TM

For the procedure to be algorithmic the TM should stop. But Turing and Church showed that there is no algorithmic procedure to find out whether a given 3#3 acting on an input m will stop.

Church's thesis: The set of functions that are Turing computable is identical to the set of functions that any human or machine could compute. Turing himself identified some functions which are not Turing-computable but such functions have not been shown to be computable in any other sense either.

Apparently random behaviour can be simulated by Turing machines with transition probabilities between 0 and 1 (determinate but not predictable). Non-deterministic specifications are used to model creative processes.