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.

Related categories 1

The Alan Turing Internet Scrapbook
On-line extract from the book "Alan Turing: the enigma" by Andrew Hodges.
Turing machine
Wikipedia Article on Turing machines, containing examples, history and further references.
Turing Machine Simulator
A simulator which runs included programs such as a palindrome detector and also allows writing of programs.
Turing Machines
Article in Stanford Encyclopedia of Philosophy.
[Computer Mozilla]
Last update:
November 20, 2014 at 9:05:08 UTC
Computers
Games
Health
Home
News
Recreation
Reference
Regional
Science
Shopping
Society
Sports
All Languages
Arts
Business