Thursday, April 19, 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 by another, possibly different symbol.

(2) Moving the tape head one square to the right or left or leaving it where it is.

(3) Moving from the current state to another, possibly different state.

The Tape serves as the input device the memory available for use during computation and the output device.

In Turing Machine processing a string is no longer restricted to a single left-to-right pass through the input.

The tape head can move in both direction and erase or modify any symbol it encounters.

The machine can examine part of the input, modify it, take time out to execute some computations in a different area of the tape, Return to reexamine the input, repeat any of these actions, and perhaps stop the processing before it has looked at all the input.

TM contains two states Ha that indicates acceptance and Hr that indicates rejection.

If the machine is intended simply to accept or reject the input string, then it can move to the appropriate halt state once it has enough information to make a decision.

If it is supposed to carry out some other computations, the accepting state indicates that the computation has terminated normally,

The state Hr can be used to indicates that the system is “Crashed”, arising from some abnormal situation in which the machine cannot carry out its mission as expected.

In any case, the computations stop if the Turing Machine reaches either of the Two Halt State.

It is also possible for the computation not to stop, and for the Turing Machine to continue making moves forever.