Church-Turing thesis

The Church-Turing thesis (named after Alonzo Church and Alan Turing , also called Church's thesis ) makes statements about the capabilities of a calculating machine. It is:

"The class of Turing-calculable functions corresponds to the class of intuitively calculable functions."

This thesis cannot be proven because the term “intuitively calculable function” cannot be precisely formalized. This is understood to mean all functions that could in principle be calculated in any way. In particular, one does not assume any idea which functions can be calculated on the natural numbers. In computer science it is usually assumed that the thesis is correct. This makes it possible to prove that a function cannot be calculated.

Emergence

Turing simulated the thought processes of a person when calculating numbers using the Turing machine he developed (similar to today's computers in terms of functionality ) and analyzed their capabilities. He found that many functions that can be thought up by a human being cannot be calculated in the first place by the Turing machine, e.g. B. the function of the holding problem .

On the other hand, it was shown that other approaches to formalizing the human way of thinking in arithmetic were not more successful: Historically, Turing was the first to prove the equivalence of Church's Lambda calculus to the Turing machine. This was followed by many other proposed algorithmic terms (computational models), all of which were no more computational than the Turing machine. These algorithm terms are therefore called Turing-complete .

This suggested that there was no more powerful formalism than that of the Turing machine with regard to calculability and that humans - also working algorithmically - could no longer calculate more functions . This gave rise to the Church-Turing thesis.

Implications

If the thesis is true, there can be no computer model that can calculate more than the previous models. In particular, a computer is such a computer model, so theoretically any algorithm can be executed on it, provided that there is enough memory available. It is then not possible to build a calculating machine that can calculate more than a computer can already. Since many programming languages are also Turing-complete, any algorithm can be expressed using a source code of these languages. In particular, different computing models (e.g. register machines , Turing machines , GOTO programs , WHILE programs , µ-recursive functions ) can simulate each other.

If the thesis is wrong, the mentioned implications do not apply. A refutation of the thesis would be possible with the construction of a hypercomputer that can perform calculations that are not possible on a Turing machine.

Extended Church thesis

The Advanced Church's thesis goes one step further. It is:

"For every two computer models and there is a polynomial so that calculation steps on the model can be simulated with calculation steps on the model when the length is entered ." ${\ displaystyle R_ {1}}$ ${\ displaystyle R_ {2}}$ ${\ displaystyle p}$ ${\ displaystyle t}$ ${\ displaystyle R_ {1}}$ ${\ displaystyle n}$ ${\ displaystyle p (t, n)}$ ${\ displaystyle R_ {2}}$

In the face of quantum computers , it is now assumed that this stronger thesis is incorrect. For example, Shors' algorithm is able to factor numbers in polynomial time , while the best known algorithms for regular Turing machines cause super-polynomial effort.

Further algorithm terms

literature

Douglas R. Hofstadter : Gödel, Escher, Bach - an endless braided band . (Chapter 17).
Alan Turing : On Computable Numbers, with an Application to the Decision Problem . In: Proceedings of the London Mathematical Society . Series 2, Vol. 42, 1936, ISSN 0024-6115 , pp. 230-265 .
Hans Hermes : Enumerability, decidability, predictability . 2nd Edition. Springer Berlin, Heidelberg, New York, 1971, ISBN 3-540-05334-4 .

Individual evidence

↑ Dirk W. Hoffmann : Theoretical Computer Science. 2nd updated edition. Carl Hanser Fachbuchverlag, Munich 2011, ISBN 978-3-446-42639-9 , p. 308.

[1] Dirk W. Hoffmann : Theoretical Computer Science. 2nd updated edition. Carl Hanser Fachbuchverlag, Munich 2011, ISBN 978-3-446-42639-9 , p. 308.