Proof of Church Thesis


Click here to return to the main page

doi: 10.6084/m9.figshare.4955501


Definition

In this paper, we use Church’s thesis as formulated by Gandy (1980):

Church’s thesis: What is effectively calculable is computable.

Abstract

We prove that if our calculating capability is limited to that of a universal Turing machine with a finite tape, then Church's thesis is true. This way we accomplish Post (1936) program.

Background

Post (1936) sketched a device very similar to a Turing machine, and in the very last paragraph he presented a program that interpreted Church’s thesis as a "natural law" stating "the limitations of the mathematicizing power of [Homo sapiens]". As any natural law, it was in "need of its continual verification." These are the two last sentences of the paper by Post.
The success of the above program would, for us, change this hypothesis not so much to a definition or to an axiom but to a natural law. Only so, it seems to the writer, can Gödel’s theorem concerning the incompleteness of symbolic logics of a certain general type and Church’s results on the recursive unsolvability of certain problems be transformed into conclusions concerning all symbolic logics and all methods of solvability.

Church's reaction was bipolar.

Davis (1982) provides a more detailed explanation of the history of Church’s thesis. There, you can learn about Gödel’s position on Church’s thesis in 1934, as explained by Church himself in a letter to Kleene:
His [Gödel’s] only idea at the time [early in 1934] was that it might be possible, in terms of effective calculability as an undefined notion, to state a set of axioms which would embody the generally accepted properties of this notion, and to do something on that basis.

My position

I agree completely with Post (1936). To me, Church’s thesis is neither a definition, as argued by Church, nor an axiom, as preferred by Gödel, but a natural law stating the calculating limitations of the members of our own species Homo sapiens. In fact, in my theory, see The Intention of Intention and On Turing Completeness, Post's law is the fundamental law of cognition.

Law of Post: In calculating capacity, we are just Turing complete.

Effective Computation

Sometimes a natural law is defined in an ideal world, then appearing to us as an approximation. For example, Newton’s first law of motion requires an ideal frictionless world. Similarly, in this paper, we find a provision for translating ideal computing to real computing: "save for time or tape limitations".


References

Link to the page of my "proof" of the Church-Turing thesis in figshare, and direct link to the pdf file.

Another version is in the arXiv, with its pdf file.

These are the external references used in his page:


Última actualización: 2019-09-11.

© Ramón Casares 2019