en.wikipedia.org, 2022-09-19 | Main page
Saved from web.archive.org, with Lynx.
   #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.
   [ ]


     * 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.


   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

   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.


   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

   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

Unintentional Turing completeness[edit]

   Some games and other software are Turing-complete by accident, i.e. not
   by design.

     * 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]

     * 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)


    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.


    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.
    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
    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
   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
   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

     * 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


     * Article
     * Talk

   [ ] English


     * Read
     * Edit
     * View history

   [ ] More


   ____________________ Search Go


     * Main page
     * Contents
     * Current events
     * Random article
     * About Wikipedia
     * Contact us
     * Donate


     * Help
     * Learn to edit
     * Community portal
     * Recent changes
     * Upload file


     * What links here
     * Related changes
     * Upload file
     * Special pages
     * Permanent link
     * Page information
     * Cite this page
     * Wikidata item


     * Download as PDF
     * Printable version


     * 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
Saved from web.archive.org, with Lynx.
Main page
© 2022 Matei. No cookies®