Turing Machines

1. Algorithms

No precise definition of an algorithm. Common features include:

• finite description of the procedure in terms of elementary operations.
• deterministic, next step uniquely determined if there is one.
• procedure may not terminate on some input data, but we can recognise when it does terminate and what the result is.

2. Turing Machines

The machine starts with state with the tape head pointing to the first symbol of the finite input string. The machine computes in steps, each depending on the current state and the symbol being scanned by the tape head . An action at each step is to:

• Overwrite the current tape ell with a symbol.
• Move left or right one cell.
• Change state.

2.1 Formal Definition

A turing machine is specified by a quadruple where:

• is a finite set of machine states.
• is a finite set of tape symbols, containing a blank symbol .
• is the initial state.
• is the transition function.

A turing machine configuration consists of:

• is the current state.
• is the left tape content.
• is the right tape content.

The initial configuration is given by where is the input string and is the initial state.

Define the functions: and as:

These functions split of the first and last symbols of a string.

NOTE: in this case, denotes a character followed by a string , and denotes a string followed by a character .

Given , define by:

Or, in english:

• If the machine is in state , reads symbol from the tape, and the transition function says to move left, then the machine moves to state , writes symbol to the tape, and moves left.
• If the machine is in state , reads symbol from the tape, and the transition function says to move right, then the machine moves to state , writes symbol to the tape, and moves right.

We say that a configuration is in normal form if it has no computation step. This is exactly the case when is undefined for .

The computation of a turing machine is an infinite sequence of configurations such that:

• is the initial configuration.

The computation halts iff:

• The sequence is finite.
• The last configuration is in normal form.

2.2 Graphical Representation

Consider the turing machine where , , and is defined by:

Let's define a graph representing a turing machine as:

• Nodes are states .
• Edges represent the transition function .
• For , with , , and , we draw an edge from to labeled by .
• Initial State is marked by an unlabeled edge.

Now, for the example above, our graph is:

3. Mapping to Register Machines

To prove that any turing machine may be mapped to register machines:

1. Fix a numerical encoding of 's states, tape symbols, tape contents and configurations.
2. Implement 's transition function as a register machine program.
3. Implement a register machine program that repeatedly applies .

3.1 Encoding

• We can identify states and tape symbols with numbers as and where and .
• Code configurations can be encoded as where:
  • , the current state.
  • , the left tape content (where ).
  • , the right tape content (where ).
• Identify directions with numbers and .

3.2 Transition Function

We can turn the finite specification of into an RM gadget:

If , , and are the initial values of registers , and :

• Updates the registers to , , and and takes the defined exit if .
• Leaves the registers unchanged and takes the undefined exit if is undefined.

3.3 Turing Register Machine

Now, we can create a register machine which implements the computation of a turing machine . The registers are:

• for the current state.
• for the left tape content (right to left).
• for the right tape content (left to right).

Starting with containing the input string, and all other registers zeroed, the program halts iff halts, and in that case, , , and contain the final configuration.

4. Tape Encoding of Lists of Numbers

A tape over codes a list of numbers as:

5. Turing Computable Functions

is turing computable iff there is a turing machine such that starting from its initial state with tapehead on the leftmost on a tape coding , halts iff and in that case, the final tape codes a list whose first element is where .

A partial function is turing computable iff it is register machine computable. We can implement a turing machine with a register machine, so being turing computable implies is register machine computable. For the converse, one has to implement the computation of a register machine in terms of a turing machine operating on a tape coding register machine configurations. To do this, one has to show how to carry out the action of each type of RM instruction on the tape. It should be reasonably clear that this is possible in principle, even if the details are omitted.