Click here to return to the main page

doi: 10.6084/m9.figshare.4955501

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

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.

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 publish 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.
*

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.

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*.

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:

- 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.

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

© Ramón Casares 2019