FOM: physical computability
shapiro+ at osu.edu
Tue Aug 22 21:35:37 EDT 2000
There has been some discussion here lately of the possibility of building a
machine that computes a non-recursive function (and so would refute at
least some versions of Church's thesis).
I cannot follow all of the technical details of the discussion, and have
only a flat-footed observation to make.
Suppose that we either describe or actually build a (physical) machine M,
and someone claims that M computes a non-recursive function (say, to be
fanciful, M is claimed to be a decision procedure for arithmetic truth, or
for the halting problem). How could we verify this claim?
No amount of empirical data could verify the claim about M. We can observe
only a finite amount of the actual behavior of M, and the thesis that M
computes a recursive function is consistent with any finite chunk of data.
Perhaps some physical theory would entail that M computes a non-recursive
function. Suppose that this theory T, plus the description D of M, allows
us to calculate the values of the function computed by M for any given
input. In this case, we would have a more standard refutation of Church's
thesis (if there is such a thing). That is, T+D would constitute an
algorithm for computing a non-recursive function (even if T happens to be
false physics, it would still allow the algorithm).
As far as I can see, the only way we would have a specifically physical
refutation of Church's thesis would be if T+D somehow entailed that M
computes a non-recursive function without showing us how to compute the
values of this function (short of building M and letting it run).
It seems that issues of determinism are wrapped in here.
More information about the FOM