Computability theory

from Wikipedia, the free encyclopedia

The computability theory (also recursion theory ) is a branch of theoretical computer science and mathematical logic that deals with the concept of computability , in particular with which problems with the help of a machine (more precisely: a mathematical model of a machine) or another mathematical model of the Predictability are solvable. It is closely related to formal semantics , but focuses more on the termination of programs and algorithms .

The central question of recursion theory is which functions (or sets) can be calculated with which computability model. For this purpose, models for predictability and their performance are examined. The type of calculation models considered results in a fuzzy demarcation from complexity theory , in which mainly calculation models with resource restrictions are considered. The focus of many investigations in recursion theory is the relative computability of functions, i.e. That is, which functions can be calculated with a given function using a specific calculation model (see for example under Turing degrees ).

Main questions

How can one formalize the concept of intuitive predictability ? As a widely recognized answer, the Turing machine has established itself as a possible model ( Church-Turing thesis ). It was recognized that the computational ability of the Turing machine is equivalent to many other computation models.

What kind of tasks can which class of machines solve? In particular, deterministic and nondeterministic variants of the following models are examined:

What kind of problems need more powerful machines?

What kind of tasks can a Turing machine solve?

A problem is said to be decidable if it can be solved by an algorithm that terminates after a finite number of steps. Many problems are decidable, but there are also known many undecidable problems. For example, according to Rice's theorem, all (non-trivial) semantic properties of programs are undecidable.

For example, the problem of the validity of predicate logic formulas cannot be solved algorithmically: A statement of the first-order predicate logic is given . The task is to find out whether the statement is true. This problem is also known as the decision problem (in the narrower sense). Church and Turing have independently demonstrated that this problem cannot be solved.

Another problem is the holding problem . Let there be an algorithm and an input. It is asked whether the algorithm for the input finally stops (terminates). Turing demonstrated the undecidability of this question.

Different models of predictability with equal performance

Which tasks can be solved by less powerful machines?

The Chomsky hierarchy describes those formal languages ​​that can be recognized by four classes of algorithms. They all assume a nondeterministic finite automaton with a memory. If the memory is infinitely large, then the situation corresponds to the Turing machine. If the memory is proportional to the size of the input string, then contextual languages ​​can be recognized. If the memory contains only one stack, then context-free languages ​​can be recognized. If the machine has only finite memory, then only languages ​​that are defined by regular expressions can be recognized.

Connection with physics

The physicist Richard Feynman noticed that computers are pretty bad at calculating problems from quantum mechanics. An important lecture by him on this in 1981 had the title

Can (quantum) physics be (efficiently) simulated by (classical) computers?

Obviously, nature can calculate the outcome of a quantum mechanical experiment faster than we can with a computer. So he suggested building a special computer, a quantum processor. Its arithmetic unit should use quantum mechanical processes to calculate results for quantum mechanical problems more efficiently. At some point it became clear that the simple mathematical models of theoretical computer science can actually only correspond with a sub-class of real computers, because all physical possibilities had not been exhausted. This new class of computers is known as quantum computers . In spite of this, quantum computers are no more powerful than Turing machines in the sense of the computability theory (they can solve exactly the same problems), but there could possibly be a considerable speed advantage.

literature

Introductions

  • S. Barry Cooper: Computability Theory. Chapman & Hall / CRC, Boca Raton FL et al. 2004, ISBN 1-58488-237-9 .
  • Nigel Cutland: Computability. An introduction to recursive function theory. Cambridge University Press, Cambridge et al. 1980, ISBN 0-521-29465-7 .
  • Klaus Heidler, Hans Hermes , Friedrich-K. Reminder: recursive functions. Bibliographisches Institut, Mannheim et al. 1977, ISBN 3-411-01535-7 .
  • Hans Hermes: Enumerability - Decidability - Calculability. Introduction to the theory of recursive functions (= The basic teachings of the mathematical sciences. 109, ISSN  0072-7830 ). Springer, Berlin et al. 1961 (2nd edition. Ibid 1971, ISBN 3-540-05334-4 , as Heidelberger Taschenbuch. 87).
  • Stephen Cole Kleene : Introduction to Metamathematics (= Bibliotheca Mathematica. 1, ZDB -ID 419838-4 ). Amsterdam et al., North-Holland et al. 1952.
  • Michael Sipser : Introduction to the Theory of Computation. PWS Publishing, Boston MA et al. 1997, ISBN 0-534-94728-X , Part Two: Computability Theory. Chapters 3-6, pp. 123-222.

Special works

  • Piergiorgio Odifreddi : Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers. 2 volumes. Elsevier, Amsterdam et al. 1989–1999;
    • Volume 1. (= Studies in Logic and the Foundations of Mathematics. 125). 1989, ISBN 0-444-87295-7 ;
    • Volume 2. (= Studies in Logic and the Foundations of Mathematics. 143). 1999, ISBN 0-444-50205-X .
  • Hartley Rogers, Jr .: Theory of recursive functions and effective computability . McGraw-Hill, New York NY et al. 1967.
  • Gerald E. Sacks : Higher Recursion Theory. Springer, Berlin et al. 1990, ISBN 3-540-19305-7 .
  • Robert I. Soare: Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets (= Perspectives in Mathematical Logic. ). Springer, Berlin et al. 1987, ISBN 0-387-15299-7 .

Individual evidence

  1. ^ Richard P. Feynman : Simulating Physics with Computers. In: International Journal of Theoretical Physics. Vol. 21, No. 6/7, 1982, ISSN  0020-7748 , pp. 467-468, doi : 10.1007 / BF02650179 .
  2. ^ Tony Hey: Richard Feynman and Computation. In: Contemporary Physics. Vol. 40, No. 4, 1999, ISSN  0010-7514 , pp. 257-265, doi : 10.1080 / 001075199181459 .