Difference between revisions of "Turing machine"
Karl Jones (Talk | contribs) (→See also) |
Karl Jones (Talk | contribs) |
||
| (3 intermediate revisions by the same user not shown) | |||
| Line 29: | Line 29: | ||
* [[Computer science]] | * [[Computer science]] | ||
* [[Entscheidungsproblem]] | * [[Entscheidungsproblem]] | ||
| + | * [[Finite-state machine]] | ||
* [[Lambda calculus]] | * [[Lambda calculus]] | ||
* [[Non-deterministic Turing machine]] | * [[Non-deterministic Turing machine]] | ||
| Line 40: | Line 41: | ||
* [https://en.wikipedia.org/wiki/Turing_machine Turing machine] @ Wikipedia | * [https://en.wikipedia.org/wiki/Turing_machine Turing machine] @ Wikipedia | ||
| + | * [http://webturingmachine.appspot.com/ Web Turing machine] @ appspot.com | ||
| + | |||
| + | [[Category:Alan Turing]] | ||
| + | [[Category:Algorithms]] | ||
| + | [[Category:Computation]] | ||
| + | [[Category:Computer science]] | ||
| + | [[Category:Logic]] | ||
| + | [[Category:Mathematics]] | ||
| + | [[Category:Symbols]] | ||
| + | [[Category:Turing machines]] | ||
Latest revision as of 13:30, 27 October 2017
A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules.
Description
Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm.
At a very high level, the machine consists of a memory tape divided into cells.
A "head" (e.g. a pencil/eraser) traverses the memory one cell at a time, writing or erasing data (e.g. numerical digits) based on user-specified rules.
The "machine" was invented in 1936 by Alan Turing who called it an "a-machine" (automatic machine).
The Turing machine is not intended as practical computing technology, but rather as a hypothetical device representing a computing machine.
Turing machines help computer scientists understand the limits of mechanical computation.
Turing completeness is the ability for a system of instructions to simulate a Turing machine.
Programming languages
A programming language that is Turing complete is theoretically capable of expressing all tasks accomplishable by computers.
Nearly all non-markup programming languages are Turing complete.
See also
- Abstract machine
- Church, Alonzo
- Computer science
- Entscheidungsproblem
- Finite-state machine
- Lambda calculus
- Non-deterministic Turing machine
- Programming language
- Theoretical computer science
- Turing, Alan
- Turing completeness
- Universal Turing machine
External links
- Turing machine @ Wikipedia
- Web Turing machine @ appspot.com
