Turing machine (nonfiction): Difference between revisions

From Gnomon Chronicles
Jump to navigation Jump to search
No edit summary
 
(14 intermediate revisions by the same user not shown)
Line 1: Line 1:
A '''Turing machine''' is a hypothetical device that manipulates [[Symbol|symbols]] on a strip of tape according to a table of rules.
[[File:TuringBeispielAnimatedGIF.gif|right|frame|Animated diagram of a Turing machine.]]A '''Turing machine''' is a hypothetical device that manipulates [[Symbol|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.
Despite its simplicity, a Turing machine can be adapted to simulate the [[logic (nonfiction)]] of any computer algorithm.
Line 17: Line 15:
[[Turing completeness (nonfiction)]] is the ability for a system of instructions to simulate a Turing machine.
[[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]] is theoretically capable of expressing all tasks accomplishable by computers.
 
== In the News ==
 
<gallery mode="traditional">
</gallery>


A [[programming language]] that is [[Turing completeness|Turing complete]] is theoretically capable of expressing all tasks accomplishable by computers.
== Fiction cross-reference ==


Nearly all [[non-markup programming languages]] are Turing complete.
* [[Alan Turing]]
* [[Turing machine]]


== Nonfiction cross-reference ==
== Nonfiction cross-reference ==
Line 27: Line 31:
* [[Alan Turing  (nonfiction)]]
* [[Alan Turing  (nonfiction)]]
* [[Alonzo Church (nonfiction)]]
* [[Alonzo Church (nonfiction)]]
* [[Computation (nonfiction)]]
* [[Computer science (nonfiction)]]
* [[Computer science (nonfiction)]]
* [[Entscheidungsproblem (nonfiction)]]
* [[Lamplighter group (nonfiction)]] -
* [[Lambda calculus (nonfiction)]]
* [[Mathematics (nonfiction)]]
* [[Mathematics (nonfiction)]]
* [[Theoretical computer science (nonfiction)]]
* [[Quantum simulator (nonfiction)]]
* [[Theory of computation (nonfiction)]]
* [[Turing completeness (nonfiction)]]
* [[Turing completeness (nonfiction)]]
* [[Universal Turing machine (nonfiction)]]


== Fiction cross-reference ==
External links:
 
* [[Alan Turing]]
* [[Turing machine]]
 
== External links ==


* [http://wiki.karljones.com/index.php?title=Turing_machine Turing machine] @ wiki.karljones.com
* [https://en.wikipedia.org/wiki/Turing_machine Turing machine] @ Wikipedia
* [https://en.wikipedia.org/wiki/Turing_machine Turing machine] @ Wikipedia



Latest revision as of 08:46, 4 February 2018

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.

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.

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

In the News

Fiction cross-reference

Nonfiction cross-reference

External links: