Turing machine (nonfiction)

Animated diagram of a Turing machine.

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 (nonfiction) 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 (nonfiction) 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 (nonfiction) is the ability for a system of instructions to simulate a Turing machine.

Programming languages

A programming language that is Turing complete (nonfiction) is theoretically capable of expressing all tasks accomplishable by computers.

Nearly all non-markup programming languages are Turing complete.

Nonfiction cross-reference

• Alan Turing (nonfiction)
• Alonzo Church (nonfiction)
• Computer science (nonfiction)
• Entscheidungsproblem (nonfiction)
• Lambda calculus (nonfiction)
• Mathematics (nonfiction)
• Theoretical computer science (nonfiction)
• Turing completeness (nonfiction)

Fiction cross-reference

• Alan Turing
• Turing machine

External links

• Turing machine @ wiki.karljones.com
• Turing machine @ Wikipedia