Directory of Turing Machines Resources

Home > Computers > Computer Science > Theoretical > Automata Theory > Turing Machines

A Turing machine is an imaginary computing machine invented by Alan Turing to describe what it means to compute something. The “physical description” of a Turing machine is a box with a tape and a tape head. The tape consists of an infinite number of cells stretching in both directions, with the tape head always located over exactly one of these cells. Each cell has one of a finite number of symbols written on it. The machine has a finite set of states, and with every move the machine can change states, change the symbol written on the current cell, and move one space left or right. The machine has a program which specifies each move based on the current state and the symbol under the current cell. The machine stops when it reaches a combination of state and symbol for which no move is defined. A countable set S (or language) is called recursively enumerable if there exists a Turing machine that always halts when given an element of S as input, and that never halts when given an input that does not belong to S.

Resources in This Category

• The Alan Turing Internet Scrapbook

  http://www.turing.org.uk/turing/scrapbook/machine.html
  On-line extract from the book "Alan Turing: the enigma" by Andrew Hodges.

• Turing machine

  http://en.wikipedia.org/wiki/Turing_machine
  Wikipedia Article on Turing machines, containing examples, history and further references.

• Turing Machine Simulator

  http://ironphoenix.org/tril/tm/
  A simulator which runs included programs such as a palindrome detector and also allows writing of programs.

• Turing Machines

  http://plato.stanford.edu/entries/turing-machine/
  Article in Stanford Encyclopedia of Philosophy.

Related Categories

• Home > Computers > Computer Science > Theoretical > Formal Language Theory > Recursively Enumerable Languages

 

Home > Computers > Computer Science > Theoretical > Automata Theory > Turing Machines

 

---

 

Thanks to DMOZ, which built a great web directory for nearly two decades and freely shared it with the web. About us