---------------------------------------------------------------------------------------
.
---------------------------------------------------------------------------------------
#alternate Edit this page Wikipedia (en)
Turing completeness
From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Ability of a computing system to simulate Turing machines
For the usage of this term in the theory of relative computability by
oracle machines, see Turing reduction.
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 Turing machine (devised by English
mathematician and computer scientist Alan Turing). This means that this
system is able to recognize or decide other data-manipulation rule
sets. Turing completeness is used as a way to express the power of such
a data-manipulation rule set. Virtually all programming languages today
are Turing-complete.
A 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. The
Church-Turing thesis conjectures that any function whose values can be
computed by an algorithm can be computed by a Turing machine, and
therefore that if any real-world computer can simulate a Turing
machine, it is Turing equivalent to a Turing machine. A universal
Turing machine can be used to simulate any Turing machine and by
extension the computational aspects of any possible real-world
computer.^[NB 1]
To show that something is Turing-complete, it is enough to show that it
can be used to simulate some Turing-complete system. No physical system
can have infinite memory, but if the limitation of finite memory is
ignored, most programming languages are otherwise Turing-complete.
[ ]
Contents
* 1 Non-mathematical usage
* 2 Formal definitions
* 3 History
* 4 Computability theory
* 5 Turing oracles
* 6 Digital physics
* 7 Examples
+ 7.1 Unintentional Turing completeness
* 8 Non-Turing-complete languages
* 9 See also
* 10 Notes
* 11 References
* 12 Further reading
* 13 External links
Non-mathematical usage[edit]
In colloquial usage, the terms "Turing-complete" and
"Turing-equivalent" are used to mean that any real-world
general-purpose computer or computer language can approximately
simulate the computational aspects of any other real-world
general-purpose computer or computer language. In real life this leads
to the practical concepts of computing virtualization and
emulation.^[citation needed]
Real computers constructed so far can be functionally analyzed like a
single-tape Turing machine (the "tape" corresponding to their memory);
thus the associated mathematics can apply by abstracting their
operation far enough. However, real computers have limited physical
resources, so they are only linear bounded automaton complete. In
contrast, a universal computer is defined as a device with a
Turing-complete instruction set, infinite memory, and infinite
available time.
Formal definitions[edit]
In computability theory, several closely related terms are used to
describe the computational power of a computational system (such as an
abstract machine or programming language):
Turing completeness
A computational system that can compute every Turing-computable
function is called Turing-complete (or Turing-powerful).
Alternatively, such a system is one that can simulate a
universal Turing machine.
Turing equivalence
A Turing-complete system is called Turing-equivalent if every
function it can compute is also Turing-computable; i.e., it
computes precisely the same class of functions as do Turing
machines. Alternatively, a Turing-equivalent system is one that
can simulate, and be simulated by, a universal Turing machine.
(All known physically-implementable Turing-complete systems are
Turing-equivalent, which adds support to the Church-Turing
thesis.^[citation needed])
(Computational) universality
A system is called universal with respect to a class of systems
if it can compute every function computable by systems in that
class (or can simulate each of those systems). Typically, the
term 'universality' is tacitly used with respect to a
Turing-complete class of systems. The term "weakly universal" is
sometimes used to distinguish a system (e.g. a cellular
automaton) whose universality is achieved only by modifying the
standard definition of Turing machine so as to include input
streams with infinitely many 1s.
History[edit]
Turing completeness is significant in that every real-world design for
a computing device can be simulated by a universal Turing machine. The
Church-Turing thesis states that this is a law of mathematics - that a
universal Turing machine can, in principle, perform any calculation
that any other programmable computer can. This says nothing about the
effort needed to write the program, or the time it may take for the
machine to perform the calculation, or any abilities the machine may
possess that have nothing to do with computation.
Charles Babbage's analytical engine (1830s) would have been the first
Turing-complete machine if it had been built at the time it was
designed. Babbage appreciated that the machine was capable of great
feats of calculation, including primitive logical reasoning, but he did
not appreciate that no other machine could do better.^[citation needed]
From the 1830s until the 1940s, mechanical calculating machines such as
adders and multipliers were built and improved, but they could not
perform a conditional branch and therefore were not Turing-complete.
In the late 19th century, Leopold Kronecker formulated notions of
computability, defining primitive recursive functions. These functions
can be calculated by rote computation, but they are not enough to make
a universal computer, because the instructions that compute them do not
allow for an infinite loop. In the early 20th century, David Hilbert
led a program to axiomatize all of mathematics with precise axioms and
precise logical rules of deduction that could be performed by a
machine. Soon it became clear that a small set of deduction rules are
enough to produce the consequences of any set of axioms. These rules
were proved by Kurt Goedel in 1930 to be enough to produce every
theorem.
The actual notion of computation was isolated soon after, starting with
Goedel's incompleteness theorem. This theorem showed that axiom systems
were limited when reasoning about the computation that deduces their
theorems. Church and Turing independently demonstrated that Hilbert's
Entscheidungsproblem (decision problem) was unsolvable,^[1] thus
identifying the computational core of the incompleteness theorem. This
work, along with Goedel's work on general recursive functions,
established that there are sets of simple instructions, which, when put
together, are able to produce any computation. The work of Goedel
showed that the notion of computation is essentially unique.
In 1941 Konrad Zuse completed the Z3 computer. Zuse was not familiar
with Turing's work on computability at the time. In particular, the Z3
lacked dedicated facilities for a conditional jump, thereby precluding
it from being Turing complete. However, in 1998, it was shown by Rojas
that the Z3 is capable of simulating conditional jumps, and therefore
Turing complete in theory. To do this, its tape program would have to
be long enough to execute every possible path through both sides of
every branch.^[2]
The first computer capable of conditional branching in practice, and
therefore Turing complete in practice, was the ENIAC in 1946. Zuse's Z4
computer was operational in 1945, but it did not support conditional
branching until 1950.^[3]
Computability theory[edit]
Computability theory uses models of computation to analyze problems and
determine whether they are computable and under what circumstances. The
first result of computability theory is that there exist problems for
which it is impossible to predict what a (Turing-complete) system will
do over an arbitrarily long time.
The classic example is the halting problem: create an algorithm that
takes as input a program in some Turing-complete language and some data
to be fed to that program, and determines whether the program,
operating on the input, will eventually stop or will continue forever.
It is trivial to create an algorithm that can do this for some inputs,
but impossible to do this in general. For any characteristic of the
program's eventual output, it is impossible to determine whether this
characteristic will hold.
This impossibility poses problems when analyzing real-world computer
programs. For example, one cannot write a tool that entirely protects
programmers from writing infinite loops or protects users from
supplying input that would cause infinite loops.
One can instead limit a program to executing only for a fixed period of
time (timeout) or limit the power of flow-control instructions (for
example, providing only loops that iterate over the items of an
existing array). However, another theorem shows that there are problems
solvable by Turing-complete languages that cannot be solved by any
language with only finite looping abilities (i.e., any language
guaranteeing that every program will eventually finish to a halt). So
any such language is not Turing-complete. For example, a language in
which programs are guaranteed to complete and halt cannot compute the
computable function produced by Cantor's diagonal argument on all
computable functions in that language.
Turing oracles[edit]
Main article: Oracle machine
A computer with access to an infinite tape of data may be more powerful
than a Turing machine: for instance, the tape might contain the
solution to the halting problem or some other Turing-undecidable
problem. Such an infinite tape of data is called a Turing oracle. Even
a Turing oracle with random data is not computable (with probability
1), since there are only countably many computations but uncountably
many oracles. So a computer with a random Turing oracle can compute
things that a Turing machine cannot.
Digital physics[edit]
See also: Church-Turing thesis S: Philosophical implications
This section does not cite any sources. Please help improve this
section by adding citations to reliable sources. Unsourced material may
be challenged and removed. (November 2017) (Learn how and when to
remove this template message)
All known laws of physics have consequences that are computable by a
series of approximations on a digital computer. A hypothesis called
digital physics states that this is no accident because the universe
itself is computable on a universal Turing machine. This would imply
that no computer more powerful than a universal Turing machine can be
built physically.
Examples[edit]
The computational systems (algebras, calculi) that are discussed as
Turing-complete systems are those intended for studying theoretical
computer science. They are intended to be as simple as possible, so
that it would be easier to understand the limits of computation. Here
are a few:
* Automata theory
* Formal grammar (language generators)
* Formal language (language recognizers)
* Lambda calculus
* Post-Turing machines
* Process calculus
Most programming languages (their abstract models, maybe with some
particular constructs that assume finite memory omitted), conventional
and unconventional, are Turing-complete. This includes:
* All general-purpose languages in wide use.
+ Procedural programming languages such as C, Pascal.
+ Object-oriented languages such as Java, Smalltalk or C#.
+ Multi-paradigm languages such as Ada, C++, Common Lisp,
Fortran, JavaScript, Object Pascal, Perl, Python, R.
* Most languages using less common paradigms:
+ Functional languages such as Lisp and Haskell.
+ Logic programming languages such as Prolog.
+ General-purpose macro processor such as m4.
+ Declarative languages such as XSLT.^[4]
+ VHDL and other hardware description languages.
+ TeX, a typesetting system.
+ Esoteric programming languages, a form of mathematical
recreation in which programmers work out how to achieve basic
programming constructs in an extremely difficult but
mathematically Turing-equivalent language.
Some rewrite systems are Turing-complete.
Turing completeness is an abstract statement of ability, rather than a
prescription of specific language features used to implement that
ability. The features used to achieve Turing completeness can be quite
different; Fortran systems would use loop constructs or possibly even
goto statements to achieve repetition; Haskell and Prolog, lacking
looping almost entirely, would use recursion. Most programming
languages are describing computations on von Neumann architectures,
which have memory (RAM and register) and a control unit. These two
elements make this architecture Turing-complete. Even pure functional
languages are Turing-complete.^[5]^[NB 2]
Turing completeness in declarative SQL is implemented through recursive
common table expressions.^[6] Unsurprisingly, procedural extensions to
SQL (PLSQL, etc.) are also Turing-complete. This illustrates one reason
why relatively powerful non-Turing-complete languages are rare: the
more powerful the language is initially, the more complex are the tasks
to which it is applied and the sooner its lack of completeness becomes
perceived as a drawback, encouraging its extension until it is
Turing-complete.
The untyped lambda calculus is Turing-complete, but many typed lambda
calculi, including System F, are not. The value of typed systems is
based in their ability to represent most typical computer programs
while detecting more errors.
Rule 110 and Conway's Game of Life, both cellular automata, are
Turing-complete.
Unintentional Turing completeness[edit]
Some games and other software are Turing-complete by accident, i.e. not
by design.
Software:
* Microsoft Excel^[7]
* Microsoft PowerPoint^[8]
Video games:
* Dwarf Fortress^[9]
* Cities: Skylines^[10]
* Opus Magnum^[11]
* Minecraft^[12]
Social media:
* Habbo Hotel^[13]
Computational languages:
* C++ templates^[14]
* printf format string^[15]
Computer hardware:
* x86 MOV instruction^[16]
Biology:
* Chemical reaction networks^[17]^[18]^[19]^[20] and enzyme-based DNA
computers^[21] have been shown to be Turing-equivalent
Non-Turing-complete languages[edit]
Many computational languages exist that are not Turing-complete. One
such example is the set of regular languages, which are generated by
regular expressions and which are recognized by finite automata. A more
powerful but still not Turing-complete extension of finite automata is
the category of pushdown automata and context-free grammars, which are
commonly used to generate parse trees in an initial stage of program
compiling. Further examples include some of the early versions of the
pixel shader languages embedded in Direct3D and OpenGL
extensions.^[citation needed]
In total functional programming languages, such as Charity and Epigram,
all functions are total and must terminate. Charity uses a type system
and control constructs based on category theory, whereas Epigram uses
dependent types. The LOOP language is designed so that it computes only
the functions that are primitive recursive. All of these compute proper
subsets of the total computable functions, since the full set of total
computable functions is not computably enumerable. Also, since all
functions in these languages are total, algorithms for recursively
enumerable sets cannot be written in these languages, in contrast with
Turing machines.
Although (untyped) lambda calculus is Turing-complete, simply typed
lambda calculus is not.
See also[edit]
* AI-completeness
* Algorithmic information theory
* Chomsky hierarchy
* Church-Turing thesis
* Computability theory
* Inner loop
* Loop (computing)
* Machine that always halts
* Rice's theorem
* s[mn] theorem
* Structured program theorem
* Turing tarpit
* Virtualization
* Emulation (computing)
Notes[edit]
1. ^ A UTM cannot simulate non-computational aspects such as I/O.
2. ^ The following book provides an introduction for computation
models: Rauber, Thomas; Ruenger, Gudula (2013). Parallel
programming: for multicore and cluster systems (2nd ed.). Springer.
ISBN 9783642378010.
References[edit]
1. ^ Hodges, Andrew (1992) [1983], Alan Turing: The Enigma, London:
Burnett Books, p. 111, ISBN 0-04-510060-8
2. ^ Rojas, Raul (1998). "How to make Zuse's Z3 a universal computer".
Annals of the History of Computing. 20 (3): 51-54.
doi:10.1109/85.707574.
3. ^ Rojas, Raul (1 February 2014). Google translation, pdf is also
translatable. "Konrad Zuse und der bedingte Sprung" [Konrad Zuse
and the conditional jump]. Informatik-Spektrum (in German). 37 (1):
50-53. doi:10.1007/s00287-013-0717-9. ISSN 0170-6012.
S2CID 1086397. {{cite journal}}: External link in |others= (help)
4. ^ Lyons, Bob (30 March 2001). "Universal Turing Machine in XSLT".
B2B Integration Solutions from Unidex. Archived from the original
on 17 July 2011. Retrieved 5 July 2010.
5. ^ Boyer, Robert S.; Moore, J. Strother (May 1983). A Mechanical
Proof of the Turing Completeness of Pure Lisp (PDF) (Technical
report). Institute for Computing Science, University of Texas at
Austin. 37. Archived (PDF) from the original on 22 September 2017.
6. ^ Dfetter; Breinbaas (8 August 2011). "Cyclic Tag System".
PostgreSQL wiki. Retrieved 10 September 2014.
7. ^ "Announcing LAMBDA: Turn Excel formulas into custom functions".
TECHCOMMUNITY.MICROSOFT.COM. 3 December 2020. Retrieved 8 December
2020.
8. ^ Wildenhain, Tom (9 April 2020). "On Turing Completeness of MS
PowerPoint" (PDF).^[self-published source]
9. ^ Cedotal, Andrew (16 April 2010). "Man Uses World's Most Difficult
Computer Game to Create ... A Working Turing Machine". The Mary
Sue. Archived from the original on 27 June 2015. Retrieved 2 June
2015.
10. ^ Plunkett, Luke (16 July 2019). "Cities: Skylines Map Becomes A
Poop-Powered Computer". Kotaku. Retrieved 16 July 2019.
11. ^ Caldwell, Brendan (20 November 2017). "Opus Magnum player makes
an alchemical computer". Rock Paper Shotgun. Retrieved 23 September
2019.
12. ^ Writer, Staff. "This 8-bit processor built in Minecraft can run
its own games". PCWorld. Retrieved 21 July 2022.
13. ^ "Habbo's Twitter thread on the implementation of a Turing machine
inside the game". 9 November 2020. Retrieved 11 November 2020.
14. ^ Meyers, Scott (Scott Douglas) (2005). Effective C++ : 55 specific
ways to improve your programs and designs (3rd ed.). Upper Saddle
River, NJ: Addison-Wesley. ISBN 0321334876. OCLC 60425273.
15. ^ A 27th IOCCC Winner
Carlini, Nicolas; Barresi, Antonio; Payer, Mathias; Wagner, David;
Gross, Thomas R. (August 2015). "Control-flow bending: on the
effectiveness of control-flow integrity". Proceedings of the 24th
USENIX Conference on Security Symposium. pp. 161-176.
ISBN 9781931971232.
16. ^ Dolan, Stephen. "mov is Turing-complete" (PDF). stedolan.net.
Archived from the original (PDF) on 14 February 2021. Retrieved 9
May 2019.
17. ^ Shah, Shalin; Wee, Jasmine; Song, Tianqi; Ceze, Luis; Strauss,
Karin; Chen, Yuan-Jyue; Reif, John (4 May 2020). "Using Strand
Displacing Polymerase To Program Chemical Reaction Networks".
Journal of the American Chemical Society. 142 (21): 9587-9593.
doi:10.1021/jacs.0c02240. ISSN 0002-7863. PMID 32364723.
S2CID 218504535.
18. ^ Chen, Yuan-Jyue; Dalchau, Neil; Srinivas, Niranjan; Phillips,
Andrew; Cardelli, Luca; Soloveichik, David; Seelig, Georg (October
2013). "Programmable chemical controllers made from DNA". Nature
Nanotechnology. 8 (10): 755-762. Bibcode:2013NatNa...8..755C.
doi:10.1038/nnano.2013.189. ISSN 1748-3395. PMC 4150546.
PMID 24077029.
19. ^ Srinivas, Niranjan; Parkin, James; Seelig, Georg; Winfree, Erik;
Soloveichik, David (15 December 2017). "Enzyme-free nucleic acid
dynamical systems". Science. 358 (6369): eaal2052.
doi:10.1126/science.aal2052. ISSN 0036-8075. PMID 29242317.
20. ^ Soloveichik, David; Seelig, Georg; Winfree, Erik (23 March 2010).
"DNA as a universal substrate for chemical kinetics". Proceedings
of the National Academy of Sciences. 107 (12): 5393-5398.
Bibcode:2010PNAS..107.5393S. doi:10.1073/pnas.0909380107.
ISSN 0027-8424. PMC 2851759. PMID 20203007.
21. ^ Shapiro, Ehud (7 December 1999). "A Mechanical Turing Machine:
Blueprint for a Biomolecular Computer". Interface Focus. Weizmann
Institute of Science. 2 (4): 497-503. doi:10.1098/rsfs.2011.0118.
PMC 3363030. PMID 22649583. Archived from the original on 3 January
2009. Retrieved 13 August 2009.
Further reading[edit]
*
Brainerd, W. S.; Landweber, L. H. (1974). Theory of Computation. Wiley.
ISBN 0-471-09585-0.
Giles, Jim (24 October 2007). "Simplest 'universal computer' wins
student $25,000". New Scientist.
Herken, Rolf, ed. (1995). The Universal Turing Machine: A
Half-Century Survey. Springer Verlag. ISBN 3-211-82637-8.
Turing, A. M. (1936). "On Computable Numbers, with an Application to
the Entscheidungsproblem" (PDF). Proceedings of the London Mathematical
Society. 2. 42: 230-265. doi:10.1112/plms/s2-42.1.230. S2CID 73712.
Turing, A. M. (1938). "On Computable Numbers, with an Application to
the Entscheidungsproblem: A correction". Proceedings of the London
Mathematical Society. 2. 43: 544-546. doi:10.1112/plms/s2-43.6.544.
External links[edit]
*
"Turing Complete". wiki.c2.com.
* v
* t
* e
Alan Turing
* Turing machine
* Turing test
* Turing completeness
* Turing's proof
* Turing (microarchitecture)
* Turing degree
Retrieved from
"https://en.wikipedia.org/w/index.php?title=Turing_completeness&oldid=1
110647347"
Categories:
* Theory of computation
* Turing machine
* Programming language theory
Hidden categories:
* CS1 errors: external links
* CS1 German-language sources (de)
* All accuracy disputes
* Accuracy disputes from November 2017
* Articles with short description
* Short description matches Wikidata
* Use dmy dates from November 2017
* All articles with unsourced statements
* Articles with unsourced statements from June 2022
* Articles with unsourced statements from March 2021
* Articles with unsourced statements from December 2021
* Articles containing German-language text
* Articles needing additional references from November 2017
* All articles needing additional references
* Articles with unsourced statements from December 2010
Navigation menu
Personal tools
* Not logged in
* Talk
* Contributions
* Create account
* Log in
Namespaces
* Article
* Talk
[ ] English
Views
* Read
* Edit
* View history
[ ] More
Search
____________________ Search Go
Navigation
* Main page
* Contents
* Current events
* Random article
* About Wikipedia
* Contact us
* Donate
Contribute
* Help
* Learn to edit
* Community portal
* Recent changes
* Upload file
Tools
* What links here
* Related changes
* Upload file
* Special pages
* Permanent link
* Page information
* Cite this page
* Wikidata item
Print/export
* Download as PDF
* Printable version
Languages
* a+l+e+r+b+y+tm
* B"lgarski
* Catal`a
* Cestina
* Dansk
* Deutsch
* Ellynika'
* Espanol
* Esperanto
* f+a+r+s+
* Franc,ais
*
* Interlingua
* Italiano
* Nederlands
*
* Norsk bokmaal
* Norsk nynorsk
* Polski
* Portugues
* Russkij
* Simple English
* Srpski / srpski
* Suomi
* Svenska
* Ukrayins'ka
*
*
Edit links
* This page was last edited on 16 September 2022, at 16:53 (UTC).
* Text is available under the Creative Commons Attribution-ShareAlike
License 3.0; additional terms may apply. By using this site, you
agree to the Terms of Use and Privacy Policy. Wikipedia(R) is a
registered trademark of the Wikimedia Foundation, Inc., a
non-profit organization.
* Privacy policy
* About Wikipedia
* Disclaimers
* Contact Wikipedia
* Mobile view
* Developers
* Statistics
* Cookie statement
* Wikimedia Foundation
* Powered by MediaWiki
---------------------------------------------------------------------------------------