Turing completeness
With Turing completeness of a system to its universal programmability is described. For the adjective form Turing-complete is often used synonymously Turing powerful. The name is derived from the English mathematician Alan Turing, who introduced the model of the universal Turing machine.
Definition and application of the term
Expressed Exact referred Turing completeness in computability theory, the property of a programming language, or other logical system to be able to calculate all of the functions that can calculate a universal Turing machine. In other words, the system and a universal Turing machine can emulate each other. Even before the coining of the term of the first turing powerful mathematical formalism of Kurt Gödel was published in 1931 in his work on the incompleteness theorems.
Although such machines are physically impossible, since they would have unlimited storage, the term is applied to Turing-complete common programming languages and computers that would be universal if they possessed unlimited storage. Charles Babbage's Analytical Engine would have been Turing-complete in this sense, if it were ever built. The first machine of the Turing completeness is known for sure is the program-controlled Z3 of Konrad Zuse, which was built in 1941. However, the universality of this computer was still unknown at the time of its formation and was proved later. All modern computers are also in the broader sense Turing -complete. In 1954, Hans Hermes published one of the first proof of the Turing completeness of von Neumann computing machines, that is actually realized computer.
A machine which is Turing-complete, any calculation that can perform any computer running well and is therefore also referred to as a universally programmable. However, this results in neither a statement about the effort required to implement a particular program on such a machine, nor about the time that would be required for execution.
The computability theory is concerned with the problems using a machine with a Turing machine are especially solvable.
Examples
The common programming languages are Turing -complete. This includes conventional procedural languages, such as object-oriented languages such as C and C and Java. Even languages that were designed after less familiar paradigms, including functional programming languages such as LISP and Haskell languages and for logic programming such as Prolog, are Turing -complete.
To find examples of non- Turing - complete programming languages falls professionals difficult, as they filter the languages according to functionality and consider structural languages and purely process - oriented limited from the outset as much and they do not even take into consideration. A frequently discussed example are SGML dialects and derivatives such as - Internet users at least the name and usage by known - HTML (Hypertext Markup Language ): This structure language is in use all the given attributes quite capable, universal to keep descriptions of processes; can be described using the relational and the time- discrete control or the temporal sequence. All instrumentals, which would be necessary in the vocabulary are available. The only obstacle for inclusion in the series discussed in this article languages is the fact that HTML can not be active in it; only in addition to an active component (e.g., JavaScript), or by executing the browser in which the construct is being processed, there is the controllability and traceable time and hierarchical dependency. Since HTML is however mainly used for specific segments such as pattern libraries placeholder for dynamically generated content as passive listing for pre- recorded in the browser routines for forms and for encapsulation of processes inserted scripts, HTML is more like the aforementioned second to consider process-oriented languages , namely the batch processing and stacking coda.
Some authors define the term " programming language" based on the Turing - completeness. A sequence of formulas in a spreadsheet without loop is not Turing-complete, although it is possible to generate many interesting operations with such a system. However, the macro language in Excel ( VBA) is Turing -complete. Another well-known example are regular expressions in programming languages , editors or system tools (eg, grep, sed, ... ), where they are mainly used for pattern matching. In many implementations of regular expressions to constructs such as backreferences ( engl. back references ) be expanded, so they can not be generated by finite automata. However, they are still Turing - complete. Another example of a non- Turing complete language is the Relational algebra, since it is not possible to compute the transitive closure. In addition, the relational algebra has just not grinding.
An important conclusion from computability theory is that there can be no algorithm that can testify about any program written in a particular programming language Turing - complete if it terminates in finite time or forever remain in a loop ( see halting problem ). One way to work around this problem is to cancel a program run after a fixed period of time or lowering the thickness of control statements. However, such systems are strictly non - Turing -complete. This result was derived for example from Brainerd and Landweber of PL and PL- { GOTO } - languages.
Another theorem comes from computability theory: With a machine that has only finite loops ( for example, LOOP), it is guaranteed that each program to stop sometime. With this machine, but can not be solved all the problems that can be solved by a Turing machine, such as the Ackermann function.
The untyped lambda calculus is Turing-complete, but many type prone calculi, including system F, there are not. The advantage of type systems subject is their way, most "typical" represent computer programs, but here to discover more errors.