Turing completeness (nonfiction): Difference between revisions
No edit summary |
No edit summary |
||
| (9 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
[[File:Universal Turing machine.svg|thumb|A [[Universal Turing machine]] '''U'''. '''U''' consists of a set of instructions in the table that can | [[File:Universal Turing machine.svg|thumb|A [[Universal Turing machine]] '''U'''. '''U''' consists of a set of instructions in the table that can “execute” the correctly-formulated "code number" of any arbitrary [[Turing machine (nonfiction)|Turing machine]] '''M''' on its tape. In some models, the head shuttles back and forth between various regions on the tape. In other models the head shuttles the tape back and forth.]]In computability theory, a system of data-manipulation rules (such as a programming language) is said to be '''Turing complete''' or '''computationally universal''' if it can be used to simulate any single-taped [[Turing machine (nonfiction)|Turing machine]]. | ||
== Description == | == Description == | ||
The concept is named after English mathematician [[Alan Turing (nonfiction)|Alan Turing]]. | |||
A classic example is lambda calculus. | A classic example is lambda calculus. | ||
| Line 36: | Line 30: | ||
* [[Alan Turing]] | * [[Alan Turing]] | ||
* [[Turing machine]] | * [[Turing machine]] | ||
== External links == | == External links == | ||
* [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness] @ Wikipedia | * [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness] @ Wikipedia | ||
* [https://www.youtube.com/watch?v=sdkxWqsk17c On the Turing Completeness of PowerPoint] @ YouTube | |||
* [https://www.toothycat.net/~hologram/Turing/index.html Magic: the Gathering is Turing Complete] | |||
[[Category:Nonfiction (nonfiction)]] | [[Category:Nonfiction (nonfiction)]] | ||
[[Category:Mathematics (nonfiction)]] | [[Category:Mathematics (nonfiction)]] | ||
Latest revision as of 08:57, 13 March 2019
In computability theory, a system of data-manipulation rules (such as a programming language) is said to be Turing complete or computationally universal if it can be used to simulate any single-taped Turing machine.
Description
The concept is named after English mathematician Alan Turing.
A classic example is lambda calculus.
A closely related concept is that of Turing equivalence -- two computers P and Q are called equivalent if P can simulate Q and Q can simulate P.
According to the Church–Turing thesis, which conjectures that the Turing machines are the most powerful computing machines, for every real-world computer there exists a Turing machine that can simulate its computational aspects.
Universal Turing machine can simulate any Turing machine and by extension the computational aspects of any possible real-world computer.
Example
To show that something is Turing complete, it is enough to show that it can be used to simulate some Turing complete system.
For example, an imperative language is Turing complete if it has conditional branching (e.g., "if" and "goto" statements, or a "branch if zero" instruction.) and the ability to change an arbitrary amount of memory locations (e.g., the ability to maintain an arbitrary number of variables).
Since this is almost always the case, most (if not all) imperative languages are Turing complete if the limitations of finite memory are ignored.