5. The Church-Turing Thesis

Kevin T. Kelly
Department of Philosophy
Carnegie Mellon University

Let Eff denote the intuitive collection of intuitively effective total functions (not a set since not clearly defined).  Since it is easy to see how our ad hoc operators yield intuitively effective functions from intuitively effective functions, and since the basic functions are intuitively effective, we have:
Tot Í Eff.
I should mention, however, that this is not entirely uncontroversial.  Some finitists (e.g., Goodstein) have tried to argue that finitism stops with primitive recursion.

The converse is the Church-Turing thesis:

Eff Í Tot.
This is more troublesome.  We have defined Tot in a completely ad hoc way by adding a dumb kind of unbounded serial search on top of a dumb, restricted notion of recursion.  It would be a miracle if we caught all the intuitively effective, total functions using these two simple-minded ideas.

But perhaps miracles can happen.  Since Eff is not a mathematically defined concept (that's the whole point of defining Tot!) we can't prove that Tot = Eff.  But we can try to provide a philosophical or empirical argument for the thesis.  The two standard arguments are as follows:

I. The Amazing Coincidence Argument

No language for definining intuitively effective functions has ever yielded a definition of a function outside of Tot (although many such notations fall short of capturing all of Tot, as we have seen).  This is the argument usually quoted in textbooks.  It is a kind of physicist's argument, like discovering that the one that wave mechanics and matrix mechanics are the same theory.

The proofs are tedious but you already know more or less how they go.  Let X be a given class of functions computed by a given computational formalism.  To show

Part Í X
we show that the basic functions are in X and X is closed under the three partial recursive operators.  This is usually easy.  Conversely, to show
X  Í Part,
we proceed in a more fussy manner as follows.
  1. Use finite sequences of numbers to represent in a natural way instantaneous computational states of computations directed by program M.
  2. Code these sequences as single numbers using the primitive recursive Gödel coding.
  3. Write a primitive recursive function init(m, x) = s that converts a list x of input arguments into the Gödel code s of the initial computational state of the computation .
  4. Then we write a primitive recursive function transit(s) = s' that transforms each state code number into its successor state code number to simulate computations.
  5. Finally, we write a primitive recursive relation Output(s, y) = y that determines whether the process has yet halted with output y.
The work involved is not deep and is similar to what we did when we programmed the universal function (Cf. Cutland for lots of this).

II. Turing's Mathematician Simulation Argument

The preceding argument didn't impress either Church or Gödel, as the notations circulating at the time weren't all that different and the inter-simulation arguments were not that deep.  Perhaps everybody at the time was barking up the wrong tree.  What did impress Church and Gödel was Turing's argument based on Turing machines.  As you know from many other classes at this university, Turing computations are opaque and ugly.  Well, using them wasn't the point.  They were the linchpin of Turing's argument that Eff Í Tot.  The argument goes something like this.  Consider a mathematician following an algorithm.  The algorithm specifies a finite set of rules for modifying scribbles on a notebook in light of the current state of mind of the mathematician.  The mathematician may have boundless originality, but the states of mind relevant to following the algorithm are finite and discrete.  Also, only finite many distinct notational states can occupy a page of the scratch pad, else a microscope would be required to follow the algorithm (Turing wryly notes that Chinese characters seem to be an attempt to challenge this assumption).  Simple reduction arguments turn the scribblings into bits on a linear tape, the mathematician into a finite state automaton (for the purposes of his involvement in the computation) and the algorithm into a set of rules for elementary operations on the tape.  So the mathematician is simulated in all relevant respects by a formal Turing machine.  Let Tur denote the set of all Turing-computable functions.  The argument purports to show (philosophically) that
Eff Í Tur.
One can now prove mathematically that Tur = Part along the lines described above.  Thus
Tot = Eff.
This is what convinced Church and Gödel.

What the thesis doesn't say

Turing's reductive argument does not show that all mechanical computations are Turing computable or that human intelligence is Turing computable.  The argument that the mental state may be treated as though it were a member of a discrete, finite space works only because the mind is assumed to be working out a "mind-less" mathematical algorithm.  It is only the intutively effective or algorithmic that is treated by the argument. To extend this to arbitrary mental or mechanical processes is quite another matter.  Of course, this didn't prevent A.I. from doing so.

Arguments "by Church's Thesis"

Granting the Church-Turing thesis, any crisp procedural specification entitles us to infer that a partial recursive index exists for the function.
To compute k-ary y on inputs x, do blah blah blah.
By the Church-Turing thesis (CT), there exists an n such that y = f[n, k].
Yippee!  But don't do it until I say you may. And then make sure you provie a procedure!  CT is not an automated programming system.

Acceptable Indexings (Rogers, exercise 2-10)

In physics, it is a disaster to confuse "coordinate effects" with physical realities.  Thus, the "coriolus force" which "pulls" a projectile westward when it it shot to the north is not a force at all, but the effect of viewing rectilinear inertial motion in a rotating coordinate system.  Here is a nice metaphor:  programming languages are to computable reality as coordinate systems are to physical reality.  The analogy isn't too bad.  Physical coordinates allow us to refer to physical events.  Programs allow us to refer to computable functions.  The arbitrariness of coordinates is handled by the fact that physical laws are invariant under the relevant group of coordinate transformations.  What is the corresponding part of the analogy for computable functions?  Not physical transformations.  Not topological transformations.  Not geometrical tranformations.  You guessed it:  computable transformations.

More abstractly, sufficiently powerful computer languages may be viewed as numberings of the partial recursive functions.  To be really careful about it, a numbering of Part is a surjective (onto) mapping:

y[_,_]: N2 ® Part,
where y[i, k] denotes the ith k-ary partial recursive function according to numbering y.  Now let d, y be numberings.  Say that d[_,_] compiles into y[_,_] just in case for each k there exists a total recursive ck such that for each i, k, d[i, k] = y[ck(i), k].  "Compiles into" is a pre-order (reflexive and transitive).  Say that d[_,_] intercompiles with y[_,_] just in case each numbering compiles into the other.  Intercompilation is an equivalence relation.

Exercise 1:  To make sure you are awake and understand the definitions:  prove that compilation is a pre-order (reflexive and transitive) and that intercompilation is an equivalence relation (reflexive, transitive, and symmetric).

Our special numbering f is not arbitrary.  It has a special structure.  For example, it satisfies the universal and s-m-n theorems.  Presumably, it satisfies many other conditions as well.  But perversely enough, we will focus on these two curious properties.  Say that y is acceptable just in case  satisfies the conditions of the universal and  theorems; i.e., just in case:

  1. "k$u"n, "x Î Nk, y[u, 2](i, <x>) » y[n, lh(x)](x) [universal machine property] and
  2. "n, m, $total recrusive s "i, n-ary x, m-ary  y, y[s(i, x), n](y) » y[i, m + n](x, y) [s-m-n  property].
Now why would acceptability be of any interest?  Because it characterizes the set of all numberings intercompilable with our original numbering f.  When you stop to think that the empirical evience for the Church-Turing thesis is that all natural programming systems yield numberings intercompilable with f, we see that the universal and  theorems as it were axiomatize all the computationally invariant structure of our indexing!  That means we may kick free of all the arbitrary scaffolding and work only with the universal and s-m-n theorems! But first, as they always say, we have to prove it.  The proof is a beautiful illustration of how the universal and s-m-n constructions interact.

Proposition 1: numbering y[_,_] is acceptable Û y[_,_] is intercompilable with numbering f[_,_].

We proceed by a series of lemmas.

Lemma 2:  y[_,_] satisfies the universal machine property Þ y[_,_] compiles into f[_,_].

Proof:  Suppose that y[_,_] satisfies the universal property.  Then for some u,

(1) "n, x, y[u, 2](i, <x>) » y[i, lh(x)](x).
To get rid of the coding on the x, define:
(2) d(i, x) »y[u, 2](i, <p1, m(x), ...,pm, m(x)>).
Since rng(y[_,_]) = Part =  rng(f[_,_]), there exists a z such that
(3) d = f[z, 2].
Since f[_,_] has the s-m-n property, there is a total recursive s such that for all i, x, y,
(4) f[s(i, x), m](y)» f[i, 1 + n](x, y).
By composing in the constant function cz, we obtain the total recursive r such that:
(5) r(x) = s(z, x).
Now we use the above to calculate:
f[r(i), m](y) » [5]
f[s(z, <i>), m](y) » [4]
f[z, 1 + m](i, y) » [3]
d(i, y) »[2]
y[u, 2](i, <p1, m(x), ...,pm, m(x)>) »
y[u, 2](i, <y>) » [1]
y[i, lh(x)](x).
Thus, r(<_>) is the desired, total recursive compiler for arity m.  Yippee!

Lemma 3:  y[_,_] compiles into f[_,_] Þ y[_,_] satisfies the universal property.

 Proof:  Suppose that y[_,_] compiles into f[_,_].  Then for each k there exists a total recursive c such that

y[i, k] »f[c(i), k].
By the universal theorem for f[_,_], there is a u such that for all y:
f[c(i), m](y) »f[u, 2](c(i), <y>).
So we obtain a partial recursive function
d(i, <y>) »f[u, 2](c(i), <y>).
Since y[_,_] is onto Part, there exists a z such that for all y:
y[z, 2](i, <y>) »d(i, <y>).
Thus, for all y, we have:
y[z, 2](i, <y>) » d(i, <y>)» f[u, 2](c(i), <y>) » f[c(i), m](y) » y[i, k](y).
So z is a universal index for y[_,_].

Lemma 4:  y[_,_] satisfies the s-m-n property Þ f[_,_] compiles into y[_,_].

Exercise 1:  Prove it.

Lemma 5:  y[_,_] intercompiles with f[_,_] Þ y[_,_] satisfies the s-m-n property.

Execise 2: Prove it.