Showing posts from April 15, 2012

Turing Machine Overview

Turing Machine
An Abstract machine introduced by the English Mathematician Alan Turing and for that reason now called Turing Machine
The work of Turing and his contemporaries provided much of the theoretical foundation for the modern computer.
A Turing Machine (TM) will have a finite alphabet of symbols and a finite set of states.
TM has a linear "Tape", which has a left end and is potentially infinite to the right.
The Tape is marked off into squares, each of which can hold one symbol from the alphabet, If a square has no symbol on it, we say that it contains Blank Symbol.
We may think of squares as being numbered, Left to Right , Starting with 0. It is not necessary to refer to the numbers in describing the operation of machine.
The reading and writing being done by a tape head, which any time centered on one square of the tape.
A single move is determined by the current state and the current tape symbol, and consists of three parts.
(1) Replacing the symbol in the current square …