FOM: physical computability

[Stewart Shapiro]

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.