Church–Turing thesis

The Church - Turing thesis (named after Alonzo Church and Alan Turing, also called Church's thesis ) tells about the capabilities of a computing machine. It reads:

This thesis can not be proved, since the term " intuitively computable function " can not be precisely formalized. It refers to all the functions that can be calculated in principle in any way. This implies in particular that you have no idea what features are calculated on the natural numbers. It is usually assumed in computer science, that the thesis is true. This can make it possible to detect from a function, that it is not predictable.

Formation

On the other hand showed that other approaches to formalize the human way of thinking in arithmetic were not successful: So the equivalence of lambda calculus Churchs was historically Turing first proved the Turing machine. This was followed on many other algorithms proposed concepts ( mathematical models ), all of which are no longer rendered in their calculation ability than the Turing machine. We call these algorithms concepts accordingly as turing -complete.

This suggested that as the Turing machine would be no more powerful formalism in terms of predictability and man - also algorithmically working - also could not figure out more features. Thus, the Church - Turing thesis emerged.

Implications

If the hypothesis is true, there can be no computer model that can charge more than the previous models. In particular, a computer is one such computer model, thus to him in theory be carried out each algorithm, provided space is available. It is then not possible to build a calculating machine which can calculate more than one computer already can. Since many programming languages ​​are also turing -complete, one can express any algorithm using a source code of these languages. In particular, various computational models to simulate each other (eg, register machines, Turing machines, GOTO programs WHILE programs, μ - recursive functions).

If the theory is wrong, the above implications are not considered. A refutation of the thesis would be possible with the construction of a hypertext computer that can execute calculations, which are not possible on a Turing machine.

Extended Church's Thesis

The extended Church's thesis goes one step further. It reads:

Other algorithms concepts

  • Partial recursive function
  • Markov algorithm
  • LOOP - program (not Turing complete)
Thesis statement Halting problem Falsification LOOP (programming language)
189855
de