Turing Completeness - Examples

Examples

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
  • Universal Turing machine
  • Lambda calculus
  • Formal grammar (language generators)
  • Formal language (language recognizers)
  • Rewrite system
  • Post–Turing machines

Most programming languages, conventional and unconventional, are Turing-complete. This includes:

  • All general-purpose languages in wide use.
    • Procedural programming languages such as Pascal.
    • Object-oriented languages such as Java, Smalltalk.
    • Multi-paradigm languages such as Ada, C++, Common Lisp, Object Pascal.
  • Most languages using less common paradigms
    • Functional languages such as Lisp and Haskell.
    • Logic programming languages such as Prolog.
    • Declarative languages such as XSLT.
    • 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.

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.

Turing completeness in SQL is implemented through advanced standard features, illustrating one reason 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.

Read more about this topic:  Turing Completeness

Famous quotes containing the word examples:

    “There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
    —Bernard Mandeville (1670–1733)

    “It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
    —G.C. (Georg Christoph)

    “Histories are more full of examples of the fidelity of dogs than of friends.”
    —Alexander Pope (1688–1744)