Proof of Church’s Thesis

by Ramón Casares

Abstract

This is a proof of Church’s Thesis. I am just proposing a more basic thesis
from which Church’s Thesis is implied.

Church’s Thesis

Church’s Thesis, also known as Church-Turing Thesis, says, see [Gandy 1980]:

What is effectively calculable is computable. $None$

What is computable is anything that a Turing Machine, see [Turing 1936], can
compute. There are other definitions, using for example Church’s
$\lambda$-calculus, but all of them are equivalent (see [Turing 1936] for the
case of $\lambda$-calculus). In any case, the term computable is defined with
mathematical rigor.

But, because what can be calculated was considered a vague notion, it was
assumed that Church’s Thesis could not be formally proven. In what follows, I
will made some definitions and assumptions in order to overcome the ambiguity.

Syntax Engine

Syntax, as opposed to Semantics, is concerned with transformations of strings
of symbols, irrespective of the symbols meanings, but according to a precise
and finite set of well-defined rules. We call algorithm this set of rules.

The previous definition of Syntax generalizes the linguistic one, see [Chomsky
1957]: Syntax is the study of the principles and processes by which sentences
are constructed in particular languages. A sentence is a string of words, and
a word is a particular case of symbol.

We will assume here that persons, that is, the members of our own species homo
sapiens, have a syntactical capability. If a person speaks a particular
language, then, according to the linguistic definition, she has a syntactical
capability. Also, most of mathematics is pure Syntax, according to the general
definition, see [Hilbert 1921], and mathematics are produced and consumed by
persons.

We will call syntax engine whatever that implements a syntactical capability.
So, if persons have a syntactical capability, then each person has a syntax
engine. In the case of a general-purpose computer, the central processing unit
(CPU) is its syntax engine.

Finite Turing Machine

A Turing Machine can then be seen as a mathematical model for syntax engines,
see [Chomsky 1959]. The only part of a Turing Machine that cannot be
physically built is its infinite tape. So we will define a Finite Turing
Machine as a Turing Machine with a finite tape instead of the infinite tape.
The tape is just read and write memory.

For each Finite Turing Machine there is one corresponding Turing Machine,
which is identical to the former, except for the tape. Defining processor as
the whole Turing Machine except its tape, then any Finite Turing Machine and
its corresponding Turing Machine have the same processor.

We can also define Finite Universal Turing Machines. A Finite Universal Turing
Machine is a Universal Turing Machine, but with a finite tape, instead of the
infinite tape. As any Universal Turing Machine is a Turing Machine, see
[Turing 1936], any Finite Universal Turing Machine is a Finite Turing Machine.
The corresponding Turing Machine of a Finite Universal Turing Machine is a
Universal Turing Machine; both have the same processor.

With these definitions and considerations, we can say that the general-purpose
computer CPU is, by design, a Finite Universal Turing Machine.

Effective Computation

We will call effective computation any computation done by a Finite Turing
Machine. Effective computations are physically achievable, because Finite
Turing Machines can be physically built, as the general-purpose computer CPU
proves.

Finite Turing Machines will fail on those computations that require more tape
than they have available. Also, in practical terms, and if the tape is long,
time available could be exhausted before reaching a tape end or a HALT
instruction, and then the computation would have to be aborted, failing. These
computations that fail in the Finite Turing Machine because of a lack of
memory or a lack of time would continue in its corresponding Turing Machine,
and they will eventually succeed, or not. Summarizing: computing is more
successful than effectively computing.

But, how much successful? A computation is successful when the Turing Machine
has reached a HALT instruction in a finite time. And, whenever a computation
has reached a HALT instruction in a finite time, the Turing Machine has only
had time to inspect a finite number of tape cells. This means that any
successful computation could be done in some Finite Turing Machine in a finite
time. So the answer is: not too much.

In addition, each Finite Turing Machine computation that HALTs will be run
identically by its corresponding Turing Machine, because not limitations of
memory nor time were found, and there are not any other differences between
the two machines. So any computation done by a Finite Turing Machine will be
identically computed by its corresponding Turing Machine. Summarizing: an
effective computation is a computation.

Finite Universal Turing Machines are not universal because, taking any Finite
Universal Turing Machine, there will always be some computations that fail in
it, but that do not fail in other Finite Turing Machines that have more memory
or more time. On the other hand, any Finite Universal Turing Machine
computation that HALTs, will be run identically by its corresponding Turing
Machine, which is a Universal Turing Machine. And this means that, except for
memory or time limitations, a Finite Universal Turing Machine behaves exactly
as its corresponding Universal Turing Machine.

Calculability

We will assume the following thesis:

What is effectively calculable is what a person can calculate. $None$

This could be denied from a Platonist view of mathematics, because a super-
person, provided with a syntax super-engine, could calculate what a plain
person cannot. But, firstly, we should say that this would be “super-
calculable”, not just “calculable”, and even less “effectively calculable”.
And, secondly, if those super-calculations are outside our plain syntactical
capabilities, then we could never identify those super-calculations as
calculations, nor we could follow nor understand them.

Another objection could be that different persons can have different
calculating capabilities. This is true, but to investigate this issue, let me
present my own thesis:

Persons’ syntax engine is a Finite Universal Turing Machine. $None$

If this is the case, then, for normal persons, that is, persons without mental
disabilities, the difference can only be the amount of memory or time.

Proof

If thesis 3 is true, then, it is easy to show that Church’s Thesis (thesis 1)
is also true.

First, using thesis 2, we substitute ‘what is effectively calculable’ with
‘what a person can calculate’. Second, using the concept of syntax engine,
what a person can calculate is what her syntax engine can compute. Now, if
thesis 3 is true, that is, if persons’ syntax engine is a Finite Universal
Turing Machine, then what a person’s syntax engine can compute is what a
Finite Universal Turing Machine can compute. A Finite Universal Turing Machine
is a Finite Turing Machine, and anything that a Finite Turing Machine can
compute can also be computed by its corresponding Turing Machine, as shown in
the section on effective computation. To close this proof just remember the
first definition: anything that a Turing Machine can compute is computable.

Discussion

From the proof it is easy to see that it is also possible to imply Church’s
Thesis from a weaker assumption:

Persons’ syntax engine is a Finite Turing Machine. $None$

But this thesis 4 does not fit some facts. Because, if thesis 4 were true, but
thesis 3 were false, then some computations would be outside the syntactical
capability of persons. This would mean that persons could not follow some
Turing Machine computations. In fact, we could only calculate one algorithm.

On the other hand, the stronger thesis 3 implies thesis 4, and it is very near
to the Church’s Thesis reversed. Church’s Thesis reversed would be:

What is computable is effectively calculable. $None$

For this thesis 5 to be true, person’s syntax engine should have to be a
Universal Turing Machine, but then persons could calculate any computation,
that is, any algorithm with any data. Sadly, we persons are finite, and
therefore our syntax engine cannot has an infinite memory, nor ourselves can
have an infinite time to do calculations.

Luckily, if thesis 3 is true, and persons’ syntax engines are Finite Universal
Turing Machines, then, except for limitations of memory or time, persons can
calculate any computation. So, taking a small enough part of any computation,
persons can calculate if it is computed rightly or wrongly.

Conclusion

Turing could not had designed his Universal Machine if his own syntax engine
were not, at least, a Finite Universal Turing Machine.

For additional evolutionary arguments based on the theory of the problem
supporting thesis 3, see [Casares 2010], and [Casares 2012].

References

[Gandy 1980] Robin Gandy, “Church’s thesis and principles for mechanisms”; in
The Kleene Symposium (ed. J. Barwise et alii), North-Holland, 1980, pg 123.

[Turing 1936] Alan Turing, “On Computable Numbers, with an Application to the
Entscheidungsproblem”; in Proceedings of the London Mathematical Society,
1937, Volume s2-42, Issue 1, pp 230-265. Received 28 May, 1936. Read 12
November, 1936.

[Chomsky 1957] Noam Chomsky, Syntactic Structures, The Hague, Mouton & Co.,
1957, pg 11.

[Hilbert 1921] David Hilbert, ,,Neubegründung der Mathematik: Erste
Mitteilung“; in Abhandlungen aus dem Seminar der Hamburgischen Universität,
December 1922, Volume 1, Issue 1, pp 157-177. Series of talks given at the
University of Hamburg, July 25-27, 1921.

[Chomsky 1959] Noam Chomsky, “On certain formal properties of grammars”; in
Information and Control, June 1959, Volume 2, Issue 2, pp 137-167.

[Casares 2010] Ramón Casares, El doble compresor, isbn: 978-1-4536-0915-6,
2010.

[Casares 2012] Ramón Casares, Sobre la libertad, isbn: 978-1-4750-4270-2 / On
Freedom, isbn: 978-1-4752-8739-4, 2012.