Proof of Church's Thesis

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.

He was the editor who published the paper by Post (1936), even though he was aware of the yet unpublished paper by Turing (1936), which defined much more completely the machine and resolved the Entscheidungsproblem as unsolvable.
He wrote an unfavorable review in a later issue of the journal, Church (1937), where he argued that his thesis was not a natural law, but just a definition.

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 Subjectivist Propaganda, 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".

A finite Turing machine is a Turing machine with a finite tape instead of the infinite tape.
For each finite Turing machine there is one corresponding Turing machine, which is the Turing machine that is identical to the finite one, except for the tape.
Proposition: Save for time or tape limitations, every finite Turing machine computes exactly as its corresponding Turing machine.

References

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

Besides the DOI provided by figshare, doi: 10.6084/m9.figshare.4955501, this paper has another DOI provided by the arXiv, doi: 10.48550/arXiv.1209.5036.

These are the external references used in his page:

Church (1937): "Review of Post (1936)", doi: 10.1017/S0022481200039591.
Davis (1982): "Why Gödel Didn’t Have Church’s Thesis", doi: 10.1016/s0019-9958(82)91226-8.
Gandy (1980): "Church’s Thesis and Principles for Mechanisms", doi: 10.1016/s0049-237x(08)71257-6.
Post (1936): "Finite Combinatory Processes — Formulation 1", doi: 10.2307/2269031.
Turing (1936): "On Computable Numbers, with an Application to the Entscheidungsproblem", doi: 10.1112/plms/s2-42.1.230.

Versions:

Última actualización: 2023-03-22.