Turing Machines

Posted by ljmacphee on February 8, 2007 under topics in artificial intelligence |

Turing Machines

Automaton theory is a branch of mathematics that describes the operations of computers, especially that of Turing Machines.

A Turing machine consists of a black box, and an infinite tape. The tape is divided into blocks. Each block has one symbol. The tape head can be on one block at time, it can read or write that block and then move one block forward or one block backward. The black box has a controller, a finite memory and decides what to do based on the information read. Turing Machines can describe any finitely describable function that maps one set of strings onto another set of strings. It is believed that any function that can be computed can be computed by a Turing Machine.

A Finite State Machine is a set consisting of:
a finite set of states
a finite set of input symbols
a finite set of output symbols
the next state function
the next output function