Turing Machines

Turing Machine

The languages accepted by Turing machine are said to be recursively enumerable. A Turing Machine (TM) is a device with a finite amount of read only hard memory (states) and an unbounded amount of read/write tape memory.

Recursive languages are closed under complementation, union, intersection, concatenation and Kleene closure.
A Turing machine is said to be partially decide a problem, if the following two conditions are satisfied.
1. The problem is a decision problem.
2. The Turing machine accepts as given input if and only if the problem has an answer ‘yes’ for the input that is the Turing machine accepts the language L.
A Turing machine is said to be decide a problem, if it partially decides the problem and all its computations are halting computations.

Universal Turing Machine (UTM)

A UTM is a specified Turing machine that can simulate the behaviour of any TM.
A UTM is capable of running any algorithm.

For simulating even a simple behaviour, a Universal Turing Machine must have a large number of states. If we modify our basic model by increasing the number of read/write heads, the number of dimensions of input tape and adding a special purpose memory, then we can design a Universal Turing Machine.

Definition of Turing Machine

A Turing Machine (TM) is defined as 7-tuples.

TM = (Q, Σ, Γ, δ, q₀, b, F),

where, Q is a finite non-empty set of states, Σ is a non-empty set of input symbols (alphabets) which is a subset of Γ and b ∈ Σ, Γ is a finite non-empty set of tape symbols, δ is the transition function which maps (Q × Γ) to (Q × Γ × {L, R}), q₀ is the initial state and q₀ ∈ Q, b is the blank and b ∈ Γ, F is the set of final states and F ⊆ Q.

Transition Function of a Turing Machine

The transition function Q × Γ → Q × Γ × {L, R} states that if a Turing machine is in some state (from set Q), by taking a tape symbol (from set Γ), it goes to some next state (from set ï) by overwriting (replacing) the current symbol by another or same symbol and the read/write head moves one cell either left (L) or right (R) along the tape.