Turning Machine

A Turning Machine is a very powerful computing machine. This was invented by Alan Turning in 1936. The basic fundamental of this machine is to build an automaton with finitely many states but unbounded memory.

Parts of Turning Machine

A Turning machine basically has three main parts -

Finite State Control - It gives a command to the machine.
Infinite Tape - Memory device of machine.
Tape Head - It reads and writes a single cell.

Turning Machine Memory Device

A Turning machine is a finite automaton that has an infinite memory tape. The tape is divided into many infinite blank cells. Each cell contains a symbol from some finite alphabet. The machine operates on this tape. It has a tape head that reads and writes a single memory cell at a time. It also moves the tape cell left or right at a time. In the turning machine, this tape starts with the input written on it.

Formal Definition of Turning Machine

A Turning machine is a 7 tuple -

(Q,Σ,Γ,δ,q0,qacc,qrej)

Q - It is the finite set of states,
Σ - finite set of input alphabet,
Γ - tape alphabet,
δ - transition function, Q x Γ -> Q x Γ x {L,R},
q₀ - start state,
q_acc - accept state,
q_rej - reject state.

So, a turning machine has two alphabets, the input alphabet and the tape alphabet. The tape alphabet contains all symbols that can be written on the tape. But, it can contain at least one blank symbol. The blank symbol is denoted with □. When a Turning Machine receives an input, it can do one of the three things with the input -

• Accept the input (q_acc)
• Reject the input (q_rej)
• Continue the computing (loop)

Types of Turning Machine

There are different types of Turning Machine-

• Multi-tape Turning machine
• Multi-head Turning machine
• Non-deterministic Turning machine
• Double tape infinite tape Turning machine

Universal Turning Machine

A Turning machine that can simulate any other Turning machine is called the Universal Turning Machine. It means one turning machine acts as an input to the other turning machine.

There is a Universal Turning Machine U, it accepts encoding U(M,w) of a turning machine M and string w. It simulates the execution of M on w.

The language L_TM is the language of M.

LTM = { ⟨M, w⟩ }

+\