Computability theory

The computability theory (including recursion ) is a branch of theoretical computer science and mathematical logic, which deals with the concept of computability, in particular so that the problems with the help of a machine (more precisely: a mathematical model of a machine) are solvable. It is closely related to the formal semantics, but focuses attention more on the Terminiertheit of programs and algorithms. They also used as a starting point the various models of machines and not the abstract specification languages ​​.

The computability theory is often referred to as recursion theory. Sometimes the latter term is also used when one perceives the computability theory as a branch of mathematical logic, or to emphasize that even generalized forms of computability and definability are considered. Some authors use the term recursion, to identify only the functions with explicit self-reference.

Main questions

  • How can we formalize the notion of computability?
  • What kind of tasks can solve that class of machines? In particular, deterministic and nondeterministic variants of the following models are considered: finite state machine
  • Pushdown automaton
  • Linear time Turing machine ( LBA)
  • Turing machine
  • Register machine

What kind of tasks can solve a Turing machine?

One problem is determinable if it can be solved by an algorithm. Many problems are decidable, but there are also many undecidable problems known. For example, all ( non-trivial ) semantic properties of programs are undecidable, by the theorem of Rice.

For example, the problem of the validity predicate logic formulas not be solved algorithmically: Given is a statement of the first-order predicate logic. Task is to figure out whether the statement is true. This problem is known as the decision problem (in the narrow sense). Church and Turing have shown independently, that this problem can not be solved.

Another problem is the halting problem. Given an algorithm and input. Is asked whether the algorithm for the input holds eventually (terminated ). Turing proved the undecidability of this question.

Other models for predictability with the same performance

  • Turing machine with several bands
  • Turing machine with a two-dimensional "ribbon"
  • Register machine
  • Extended pushdown automaton with two basement storage
  • Finite state machine with two counters
  • Type 0 grammar
  • Lambda calculus
  • Recursive function
  • Extended Petri net with locking edges
  • Markov algorithm
  • Term rewriting system
  • Most modern programming languages

What 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 put a non-deterministic finite automaton ahead with a memory. When the memory is infinite, then corresponds to the situation of the Turing machine. When the memory is proportional to the size of the input string, then for context -dependent languages ​​are recognized. If the store only comprises a stack, then context-free languages ​​can be recognized. When the machine only has a finite memory, then only language defined by a regular expression can be recognized.

Connection with the physics

The physicist Richard Feynman noticed that computers are pretty bad to calculate problems in quantum mechanics. An important lecture on that program in 1981 had the title

Apparently, the nature calculate the output of a quantum mechanical experiment faster than we can with a computer. Therefore, he proposed to build a special computer, a quantum processor. Meanwhile, the calculator should take advantage of quantum mechanical processes to calculate results for quantum mechanical problems efficiently. Here then was eventually realized that the simple mathematical models in theoretical computer science can actually correspond only with a subclass of real computer, because they had not exhausted all the physical possibilities. This new class of computers is referred to as a quantum computer. Nevertheless, quantum computers in the sense of computability theory is not more powerful than Turing machines (they can exactly solve the same problems ), however a significant speed advantage could arise eventually.

117173
de