Turing completeness: Encyclopedia II - Turing completeness - Examples

Turing completeness - 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 posible, so that it would be easier to understand the limits of computation. Here are a few:

• Automata theory the standard for teaching
• universal Turing machine the classic
• Lambda calculus the original (Alonzo Church's paper predated Turing's, but Turing is credited for fuller explanation of the implications)
• formal grammar (language generators)
• formal language (language recognizers)
• rewrite system
• Post machine

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

• All general-purpose languages in wide use.
  • Imperative languages such as Ada and C
  • Object-oriented languages such as Java.
• Most languages using less common paradigms
  • Functional languages such as LISP and Haskell.
  • Logic programming languages such as Prolog.
• All or most spreadsheets, because all or most of them have more than enough logic, and can execute loops via cyclic dependencies.

The specific language 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 is an abstract statement of capability, rather than a prescription of specific language features used to implement that capability.

It is difficult to find examples of non-Turing complete languages, as these languages are very limited (see, however, machines that always halt). Example include the database language SQL, and some of the early versions of the pixel shader languages embedded in Direct3D and OpenGL extensions. Another example is a series of mathematical formulae in a spreadsheet with no cycles. While it is possible to perform many interesting operations in such a system, this fails to be Turing-complete as it is impossible to form loops; BASIC languages associated with common spreadsheet programs such as Excel and OpenOffice Calc are however Turing-complete. Another famous example is the category of regular expressions, which are generated by finite automata. A more powerful but still not Turing-complete extension of finite automata is the category of pushdown automata.

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.

Adapted from the Wikipedia article "Examples", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki