Turing completeness - Revision history

Karl Jones: /* External links */

2017-04-21T14:04:50Z

‎External links

Karl Jones: /* External links */

2017-04-20T20:12:43Z

‎External links

Karl Jones: /* External links */

2016-04-21T15:51:58Z

‎External links

Karl Jones: /* See also */

2016-03-02T19:14:18Z

‎See also

Karl Jones: /* See also */

2016-03-02T19:13:58Z

‎See also

Karl Jones at 13:23, 16 February 2016

2016-02-16T13:23:00Z

Karl Jones at 13:03, 16 February 2016

2016-02-16T13:03:04Z

Karl Jones: /* See also */

2016-02-16T13:02:10Z

‎See also

Karl Jones at 16:05, 19 August 2015

2015-08-19T16:05:52Z

Karl Jones: First

2015-08-19T16:05:01Z

First

New page

In [[computability theory]], a system of data-manipulation rules (such as a computer's instruction set, a [[programming language]], or a [[cellular automaton]]) is said to be '''Turing complete''' or '''computationally universal''' if it can be used to simulate any single-taped [[Turing machine]].

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|Universal Turing machines]] 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 programming|imperative languages]] are Turing complete if the limitations of finite memory are ignored.

== See also ==

* [[Alan Turing]]
* [[Computability theory]]
* [[Turing machine]]

== External links ==

* [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness] @ Wikipedia

@@ Line 37: / Line 37: @@
 * [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness] @ Wikipedia
-* [http://boingboing.net/2017/04/20/powerpoint-is-turing-complete.html PowerPoint is Turing complete, among other things] @ BoingBoing
+* [http://boingboing.net/2017/04/20/powerpoint-is-turing-complete.html PowerPoint is Turing complete, among other things] @ BoingBoing - a Turing-complete punchcard-driven universal machine that is embodied entirely in Powerpoint Animations and can execute any arbitrary code (albeit very slowly) and presented it at CMU's SIGBOVIK 2017 conference to great hilarity.
 [[Category:Computation]]
 [[Category:Computer science]]
 [[Category:Turing machines]]

@@ Line 37: / Line 37: @@
 * [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness] @ Wikipedia
 [[Category:Computation]]
 [[Category:Computer science]]
 [[Category:Turing machines]]

← Older revision		Revision as of 15:51, 21 April 2016
Line 37:		Line 37:

	* [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness] @ Wikipedia		* [https://en.wikipedia.org/wiki/Turing_completeness Turing completeness] @ Wikipedia
		+
		+	[[Category:Computation]]
		+	[[Category:Computer science]]
		+	[[Category:Turing machines]]

@@ Line 25: / Line 25: @@
 * [[Church–Turing thesis]]
 * [[Computability theory]]
 * [[Functional completeness]]
 * [[Lambda calculus]]

@@ Line 22: / Line 22: @@
 * [[Alan Turing]]
 * [[Computability theory]]
 * [[Functional completeness]]
 * [[Mathematical logic]]
 * [[Mathematics]]

@@ Line 5: / Line 5: @@
 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.
+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.