Computability theory
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 ( ChurchTuring 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:
 finite automaton
 Basement machine
 linear constrained Turing machine (LBA)
 Turing machine
 Register machine
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 (nontrivial) 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 firstorder 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
 Turing machine with several belts
 Turing machine with a twodimensional "band"
 Register machine
 extended cellar machine with two cellar storages
 finite automaton with two counters
 Type 0 grammar
 Lambda calculus
 recursive function
 extended Petri net with locking edges
 Markov's algorithm
 Term rewriting system
 most modern programming languages
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 contextfree 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 subclass 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 1584882379 .
 Nigel Cutland: Computability. An introduction to recursive function theory. Cambridge University Press, Cambridge et al. 1980, ISBN 0521294657 .
 Klaus Heidler, Hans Hermes , FriedrichK. Reminder: recursive functions. Bibliographisches Institut, Mannheim et al. 1977, ISBN 3411015357 .
 Hans Hermes: Enumerability  Decidability  Calculability. Introduction to the theory of recursive functions (= The basic teachings of the mathematical sciences. 109, ISSN 00727830 ). Springer, Berlin et al. 1961 (2nd edition. Ibid 1971, ISBN 3540053344 , as Heidelberger Taschenbuch. 87).
 Stephen Cole Kleene : Introduction to Metamathematics (= Bibliotheca Mathematica. 1, ZDB ID 4198384 ). Amsterdam et al., NorthHolland et al. 1952.
 Michael Sipser : Introduction to the Theory of Computation. PWS Publishing, Boston MA et al. 1997, ISBN 053494728X , Part Two: Computability Theory. Chapters 36, pp. 123222.
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 0444872957 ;
 Volume 2. (= Studies in Logic and the Foundations of Mathematics. 143). 1999, ISBN 044450205X .
 Hartley Rogers, Jr .: Theory of recursive functions and effective computability . McGrawHill, New York NY et al. 1967.
 Gerald E. Sacks : Higher Recursion Theory. Springer, Berlin et al. 1990, ISBN 3540193057 .
 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 0387152997 .
Individual evidence
 ^ Richard P. Feynman : Simulating Physics with Computers. In: International Journal of Theoretical Physics. Vol. 21, No. 6/7, 1982, ISSN 00207748 , pp. 467468, doi : 10.1007 / BF02650179 .
 ^ Tony Hey: Richard Feynman and Computation. In: Contemporary Physics. Vol. 40, No. 4, 1999, ISSN 00107514 , pp. 257265, doi : 10.1080 / 001075199181459 .