[FOM] Remarks on Church's Thesis

[Harvey Friedman]

Let me start by saying that I have never seen any formulation of
Church's Thesis that, when examined carefully, amounts to anything
more than a request for a striking result that asserts that under
unexpectedly weak conditions, some notion falls under the usual
partial recursive functions, recursive functions, r.e. sets, or
recursive sets - where the conditions are to have close connections -
never made clear - to actual computation.

So from this perspective, the real discussion begins as people propose
"proofs" of Church's Thesis, which can then be compared with each
other, and criticized from various points of view, and the process can
iterate.

For instance, any invoking of the human mind in connection with the
usual infinitary (so called) Church's Thesis is highly problematic
from the outset, since I don't know about you, but I have some
difficulty in processing numbers bigger than 2^2^2^2^10000. Perhaps I
need to expand my mind.

Similarly, any invoking of physical processes in connection with the
usual infinitary Church's Thesis is also highly problematic, as there
is no reason whatsoever to attribute any kind of infinity to the
current actual physical world. It is less problematic to think of an
infinite future in time, but then discussions about physical
experiments become more remote. The real connection between the
infinite and the physical world is rather the infinite aspects of
physical THEORIES, not physical objects or physical processes. I doubt
if any substantial number of physicists today believe in any kind of
infinitely divisible space or time or spacetime.

More coherent would be FINITE forms of Church's Thesis. Of course
there are finite models of computation, say in circuit complexity. But
I don't recall seeing formulations of finite CT.

PROOF(?) OF CT

Regardless of whether you accept the below as a proof(?), it does red
line difficulties one would have in refuting CT.

1. There will be a description of the algorithm in question and the
inputs and outputs in standard mathematical language. Inputs will have
standard formal descriptions.

2. If an input x yields the output y, then it is provable in the usual
axioms of mathematics, ZFC, that input x yields the output y.

According to 1,2, we see that the input/output relation is r.e., as
required by CT.

Harvey Friedman