Turing Machines
In 1936 Alan Turing, a British mathematician, proposed the idea of an imaginary machine able to perform all kinds of computations on numbers and symbols. Turing Machine (TM) is defined by a set of rules which define the behavior of the machine on an input/output tape. The tape is divided into (a potentially infinite number of) cells. Each cell contains a symbol or it is empty. A TM has a read/write head which moves along the tape by reading, writing and erasing symbols in the tape cells. The machine analyzes the tape, one cell at a time, starting from the cell which contains the left-most symbol in the tape. At each step, the machine reads a symbol from the tape and according to its internal state it modifies its internal state and it writes a symbol on the tape or moves its head one cell left or right.
Like a state of the mind of a human being, the internal state of a TM defines the environment in which decisions are taken.
A TM can only have a finite number of states. Formally a Turing Machine M is a 7-Tuple consisting of states Q, alphabet Σ, tape alphabet Γ, transition δ, and starting/accept/reject states q0, qaccept and qreject.
High Level description of above mention Turing Machine is as follows:
Sweep left to right across the tape crossing off every other if in stage 1 tape contained a single 0 accept. If in stage 1 tape contained more a single 0 and the number of 0 was odd, reject. Return the head to the left-hand of the tape. Go to stage 1.
Analysis of Turing Machine M:
At each iteration, stage 1 cuts the number of 0s in half.
If the resulting number of 0s is odd and greater than one, the original number could not have been a power of 2 and machine rejects
If the number of 0 is one than the original number of 0s must have been a power of 2, so machine accepts.
Multi-Tape Turing Machine
A multi-tape Turing machine with k tapes is defined in nearly the same way as a conventional single-tape Turing machine, except that it stores k strings simultaneously, (where k is the number of input tapes) maintains a position in each of the k strings, updates these k positions independently (i.e. it can move left in one string while moving right in another), and its state changes are based on the entire k-tuple of symbols that it reads at any point in time. More formally, a k-tape Turing machine has a finite alphabet and state set K as before. The difference being that the transition is determined by the entire k-tuple of symbols that it is reading, and that the instruction for the next action taken by the machine must include the symbol to be written, and the direction of motion, for each of the k strings. It is to be noted that multi-tape Turing Machine is not more powerful than single tape Turing Machine. Any multi-tape Turing machine M^ can be simulated with a single-tape Turing machine M.
Multi-Head Turing Machine
Multi –Head Turing machine is a simple Turing Machine except that it has more than one read/write heads. A multi-head Turing machine has n heads and its transition function becomes:
δ=Q x {h1, h2, h3,…hn} x Γ → Q x Γ x {L, R}
Here h1, h2, h3, hn represents each head of the Turing Machine. A n-head Turing machine can simulate a single-head one by having all transitions move only the first head and ignoring completely all the others. Nothing too hard here. This simulation will be very similar to the multi-tape simulation. However, since the distinct heads can cross each other, you’ll need to have multiple symbol modifications to represent it. Before, we had that for every symbol a we added {a} to our alphabet. Now we’re going to have to add the others. Suppose we have three heads, which we will simulate by using the symbols {}, () and ||. Then for every symbol a we have to add {a}, (a), |a|, {(a)}, {|a|}, (|a|) and {(|a|)} to our alphabet. Then, just like in the multi-tape situation, our single-head machine will scan the entire input looking for the appropriate head and modify things accordingly.
Universal Turing Machine
There is a single Turing machine U that is capable of simulating any other Turing machine; even those with vastly more states than U. In other words, one can think of U as a “Turing machine interpreter” written in the language of Turing machines. This capability for self-reference (the language of Turing machines is expressive enough to write an interpreter for itself) is the source of the surprising versatility of Turing machines and other models of computation. To define a universal Turing machine U, we must first explain what it means to give a “description” of one Turing machine as the input to another one. For example, we must explain how a single Turing machine with bounded alphabet size can read the description of a Turing machine with a much larger alphabet. To do so, we will make the following assumptions. For a Turing machine M with alphabet Σ and state set K, let:
ℓ =[log2(|Σ| + |K| + 6)]
Assume that each element of Σ ∪ K ∪ {halt, yes, no} ∪ {←, →, −} is identified with a distinct binary string in {0, 1}L. For example, we could always assume that Σ consists of the numbers 0, 1, 2, . . . , |Σ| − 1 represented as -bit binary numbers (with initial 0’s pre-pended, if necessary, to make the binary representation exactly digits long), that K consists of the numbers |Σ| , |Σ| + 1, . . . , |Σ| + | K| − 1 (with |Σ| representing the starting state s) and that {halt, yes, no} ∪ {←, →, −} consists of the numbers |Σ| + | K| , . . . , |Σ| + | K| + 5.
Now, the description of Turing machine M is defined to be a finite string in the alphabet {0, 1, ‘(’, ‘)’, ‘,’}, determined as follows: M = m, n, δ1δ2 . . . δN
Where m is the number |Σ| in binary, n is the number | K| in binary, and each of δ1, . . . , δN is a string encoding one of the transition rules that make up the machine’s transition function δ. Each such rule is encoded using a string δi = (q, σ, p, τ, d) where each of the five parts q, σ, p, τ, d is a string in {0, 1}L encoding an element of Σ ∪ K ∪ {halt, yes, no} ∪ {←, →, −} as described above. The presence of δi in the description of M indicates that when M is in state q and reading symbol σ, then it transitions into state p, writes symbol τ, and moves in direction d. In other words, the string δi = (q, σ, p, τ, d) in the description of M indicates that δ(q, σ) = (p, τ, d).
