Saturday, October 11, 2008

Turing Machine

I knew about Turing Machine from my first semester. But for some reason I feel like I should compile the basic characteristics of Turing Machine. It is worth to share here, because Turing Machine is one of the most fundamental concepts of computer science. I tried to put the very basic things about it.

Turing machines, first described by Alan Turing, are simple abstract computational devices intended to help investigate the extent and limitations of what can be computed [1].
1. A Turing machine is a kind of state machine. At any time the machine is in any one of a finite number of states. Instructions for a Turing machine consist in specified conditions under which the machine will transition between one state and another.
2. A Turing machine has an infinite one-dimensional tape divided into cells. The tape has one end, at the left say, and stretches infinitely far to the right. Each cell is able to contain one symbol, either ‘0’ or ‘1’.
3. The machine has a read-write head, which at any time scanning a single cell on the tape. This read-write head can move left and right along the tape to scan successive cells.
4. The action of a Turing machine is determined completely by
      a. The current state of the machine
      b. The symbol in the cell currently being scanned by the head and
      c. A table of transition rules, which serve as the “program” for the machine.
5. Each transition rule is a 4-tuple: < Statecurr, Symbol, Statenext, Action > which can be read as saying “if the machine is in state Statecurr and the current cell contains Symbol then move into state Statenext taking Action”.
6. The actions available to a Turing machine are either to write a symbol on the tape in the current cell, or to move the head one cell to the left or right, which we will denote by the symbols « and » respectively.
7. If the machine reaches a situation in which there is not exactly one transition rule specified, i.e., none or more than one, then the machine halts.

Some of the best sources:
[1] Turing Machine, Stanford Encyclopedia of Philosophy.
[2] Turing Machine, Wolfram Math World.
[3] Turing Machine, Famous or Infamous Wikipedia.
[4] Turing Machine, Lego Pages.
[5] Turing Machine, Encyclopedia Britannica.

No comments:

Post a Comment

Please, no abusive word, no spam.