Turing completeness

The Turing completeness of a system describes its universal programmability. For the adjective form Turing-complete , Turing- powerful is often used synonymously . 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

In precise terms, Turing completeness in computability theory describes the property of a programming language or other logical system to be able to compute all functions that a universal Turing machine can compute. In other words, the system and a universal Turing machine can emulate each other . Even before the term was coined, Kurt Gödel's first powerful mathematical formalism was published in 1931 in his work on the incompleteness theorem .

Although such machines are physically impossible since they would have to have unlimited storage space, common programming languages and computers that would be universal if they had unlimited storage space are called Turing-complete. The Analytical Engine of Charles Babbage would have been Turing complete in this sense, if it were ever built.

The Zuse Z3 was built in 1941, it was not designed to be powerful and was not used for it. As Raúl Rojas found out in 1998, it is Turing-complete via two tricks (limited calculation accuracy and sticking the perforated tape together to form a loop), but it becomes very slow.

In 1954, Hans Hermes was one of the first to publish a proof of the Turing completeness of Von Neumann computing machines, i.e. of actually realized computers. All modern computers are also Turing-complete in the broader sense.

A machine that is Turing-complete can also do any computation that any computer can do and is therefore also called universally programmable . However, this does not provide any information about the effort required to implement a specific program on such a machine , nor about the time that would be required to execute it.

The computability theory deals with which problems can be solved with the help of a machine, especially a Turing machine.

Examples

The common programming languages are Turing-complete. This includes conventional procedural languages such as C and object-oriented languages such as C ++ and Java . Languages designed according to less common paradigms , including functional programming languages such as LISP and Haskell, and logic programming languages such as Prolog , are Turing-complete. The minimalist programming languages GOTO and WHILE used in computability theory are also Turing-complete .

It is difficult for experts to find examples of programming languages that are not Turing-complete, since they filter the languages according to functionality and consider structural languages and purely process-oriented languages to be very limited from the start and do not even consider them. A frequently discussed example are SGML dialects and derivatives such as HTML , the markup language for displaying websites . If all given attributes are used, this structure language is quite capable of holding universal descriptions for processes. The time-discrete control or the time sequence can also be described with the help of the relational. All the instrumentals that would be necessary are available in the vocabulary. The only obstacle to inclusion in the series of Turing-complete languages is the fact that HTML cannot be active in itself. Only in addition to an active component, such as B. JavaScript , or the executing web browser results in controllability and traceable temporal and hierarchical dependency.

Some authors define the term “programming language” on the basis of Turing completeness.

A sequence of formulas in a spreadsheet without a loop is not Turing-complete, although it is possible to perform complex operations with such a system. In contrast, z. B. the macro language VBA for Microsoft Excel is Turing-complete.

Regular expressions in programming languages, editors or system tools (z. B. grep ), where they mainly for pattern matching to be used are not Turing-complete, even if in many implementations regular expressions to constructs such as backward references (engl. Back references be extended) that can no longer be generated by finite automata .

The Relational Algebra is not Turing complete, since it is not possible within this, the transitive closure to form. In addition, relational algebra does not have loops.

An important conclusion from computability theory is that there can be no algorithm that can say about every program written in a certain Turing-complete programming language, whether it will break off in a finite time or stay in a loop forever (see halting problem ). One method of circumventing this problem is to abort a program run after a fixed period of time or to reduce the number of control instructions. However, such systems are strictly not Turing-complete. This result was z. B. derived from land weaver .

Another theorem comes from computability theory. With a machine that only offers finite loops (for example LOOP or the primitive recursive functions equivalent to it ), it is guaranteed that every program will stop at some point. However, this machine cannot solve all the problems that can be solved by a Turing machine, e.g. B. the Ackermann function .

Μ-recursive functions are Turing-complete (hence the term recursive for decidable sets).

The untyped lambda calculus is Turing-complete, but many type-related calculi , including system F, are not. The advantage of type-based systems is their ability to display most typical computer programs, but to be able to detect more errors in the process.

literature

Walter S. Brainerd, Lawrence H. Landweber: Theory of Computation. Wiley, New York NY et al. a. 1974, ISBN 0-471-09585-0 .

Web links

Turing website of the Technical University of Central Hesse

Individual evidence

^ Alan Turing : On Computable Numbers, with an Application to the Decision Problem . In: Proceedings of the London Mathematical Society . Volume s2-42, no. 1 , 1937, p. 230-265 , doi : 10.1112 / plms / s2-42.1.230 ( PDF ).
^ Alan Turing : On Computable Numbers, with an Application to the Decision Problem. A correction . In: Proceedings of the London Mathematical Society . Volume s2-43, no. 1 , 1938, p. 544-546 , doi : 10.1112 / plms / s2-42.1.230 ( PDF ).
^ J. Fuegi, J. Francis: Lovelace & Babbage and the creation of the 1843 “notes” . In: Annals of the History of Computing . tape 25 , no. 4 . IEEE, October 2003, ISSN 1058-6180 , p. 16-26 , doi : 10.1109 / MAHC.2003.1253887 .
^ Raúl Rojas: Konrad Zuse's Legacy: The Architecture of the Z1 and Z3 . In: IEEE Annals of the History of Computing . tape 19 , no. 2 , 1997, ISSN 1058-6180 , p. 5-16 ( PDF ).
^ Raúl Rojas : How to make Zuse's Z3 a universal computer . In: Annals of the History of Computing . tape 20 , no. 3 . IEEE, 1998, ISSN 1058-6180 , pp. 51–54 , doi : 10.1109 / 85.707574 ( PDF scan , PDF , HTML ).
↑ For example Bruce MacLennan: Principles of Programming Languages . Oxford University Press, New York 1999, ISBN 0-19-511306-3 , pp. 1 .

[1] Alan Turing : On Computable Numbers, with an Application to the Decision Problem . In: Proceedings of the London Mathematical Society . Volume s2-42, no. 1 , 1937, p. 230-265 , doi : 10.1112 / plms / s2-42.1.230 ( PDF ).

[2] Alan Turing : On Computable Numbers, with an Application to the Decision Problem. A correction . In: Proceedings of the London Mathematical Society . Volume s2-43, no. 1 , 1938, p. 544-546 , doi : 10.1112 / plms / s2-42.1.230 ( PDF ).

[3] J. Fuegi, J. Francis: Lovelace & Babbage and the creation of the 1843 “notes” . In: Annals of the History of Computing . tape 25 , no. 4 . IEEE, October 2003, ISSN 1058-6180 , p. 16-26 , doi : 10.1109 / MAHC.2003.1253887 .

[4] Raúl Rojas: Konrad Zuse's Legacy: The Architecture of the Z1 and Z3 . In: IEEE Annals of the History of Computing . tape 19 , no. 2 , 1997, ISSN 1058-6180 , p. 5-16 ( PDF ).

[5] Raúl Rojas : How to make Zuse's Z3 a universal computer . In: Annals of the History of Computing . tape 20 , no. 3 . IEEE, 1998, ISSN 1058-6180 , pp. 51–54 , doi : 10.1109 / 85.707574 ( PDF scan , PDF , HTML ).

[6] For example Bruce MacLennan: Principles of Programming Languages . Oxford University Press, New York 1999, ISBN 0-19-511306-3 , pp. 1 .