Turing machines are abstract devices by means of which we can formalize any computation.
They stand at the heart of the theory of computation.

Turing machines are finite state automata.

• The head can write on the tape
• The head can move in both directions - right and left.

• Bound to the left, infinite to the right.
• Consists of cells (also called squares).
• Leftmost cell contains a special symbol (∆), to indicate the beginning of the tape.
• Each cell except the leftmost may contain a symbol from the alphabet, or a blank (□).
• Two symbols are used to denote the movement of the head to the left: ←, and to the right: →.

A Turing Machine is a quintuple (K, ∑, δ, s, H), where:

K - a finite set of states

∑ - an alphabet. ∑ contains the blank symbol □ and the left end symbol ∆, but does not contain ← and →.

s є K - the initial state

H Í K - the set of halting states

δ - the transition function.

This is a function from (K - H) x ∑ to K x (∑ È {←,→}) such that

1. for all q є K - H, if δ(q , ∆) = (p, b) then b = →

If the head is at the left end of the tape, the only possible action is
to move one position to the right.

2. for all q є K - H, and a є ∑, if δ(q , a) = (p, b) then b ≠ ∆.

It is not allowed to write on the tape the left end symbol.
Its position is fixed to be the leftmost position of the tape.

The meaning of δ(q , a) = (p, b):

1. if a is the left end symbol ∆, then M moves its head one position to the right (i.e. b = →)
2. if b є ∑ then M writes b on the tape, however it is not allowed to write ∆
3. if b = → then M moves its head to the right, preparing to read the next symbol from the tape
4. if b = ← then M moves its head one position to the left,
   preparing to read the next symbol from the tape

δ is not defined for the halting states. If M enters a halting state, then the operation stops.

The erasing machine:

The alphabet would be: ∑ = {a, □, ∆}

How many states?

1. q0 - initial state, where M reads an a.
2. q1 - where M erases the a.
3. h - a halting state

Transition function:

Tracing the operation when M is in q0, and the input tape is: ∆ a a □
(The underline shows the position of the head)

1. The first thing to be done is to move the head one position to the right.

Rule:


q0

∆

(q0, →)

Result: ∆ a a □

 

2. When in q0 and a on the tape, M enters q1 and replaces a with a blank

Rule:


q0

a

(q1, □)

Result: ∆ □ a □

 

3. When in q1 and blank on the tape, M enters q0 and moves the head one position to the right

Rule:


q1

□

(q0, →)

Result: ∆ □ a □

 

4. When in q0 and a on the tape, M enters q1 and replaces a with a blank

Rule:


q0

a

(q1, □)

Result: ∆ □ □ □

 

5. When in q1 and blank on the tape, M enters q0 and moves the head one position to the right

Rule:


q1

□

(q0, →)

Result: ∆ □ □ □

 

6. When in q0 and blank on the tape, M enters h (the halting state)

7. Rule:
   

   q0

   □

   (h, □)

    

   The operation stops.

Note that some of the transitions are never to be performed, but they are specified because
the transition relation has to be a function, otherwise the transition will not be a function.

Formally, the operation of M is described in terms of its configurations.

Configuration: determined by the current state, the state of the tape, and the position of the head.

Formal definition of a configuration:

When M is in a given configuration C1 and we apply the transition function,
another configuration C2 is obtained.
We say that C1 immediately yields C2: C1 |- C2

Initial configuration: initial state, contents of the tape, the head may be in any position

Halting configuration: halting state, any contents of the tape, any position of the head

Computation: defined as a sequence of configurations, each one immediately yielding the next,
except for the last configuration

Consider a machine that scans to the left until it finds a blank, and then stops

Trace the operation if M is in q0, and the tape is ∆ a a □