FOM: physical computability

[JoeShipman@aol.com]

In a message dated 8/22/00 10:42:44 PM Eastern Daylight Time, 
shapiro+ at osu.edu writes: (MY COMMENTS INTERPOLATED IN CAPS -- J. SHIPMAN)

<< 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. >>
UP TO THIS POINT I AM WITH YOU--THIS IS THE SCENARIO I DESCRIBE IN MY 1992 
PAPER "ASPECTS OF COMPUTABILITY IN PHYSICS".  I WILL POST A SUMMARY OF THE 
RELEVANT SECTION (THE FOM EDITORIAL BOARD REJECTED MY ORIGINAL POST WHICH 
SIMPLY QUOTED THE PAPER BECAUSE THEY DIDN'T WANT TO SET A PRECEDENT FOR 
POSTING LARGE PARTS OF PREVIOUSLY PUBLISHED WORK.)
 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).
THIS IS A STRANGE USE OF THE TERM 'ALGORITHM'.  PHYSICAL THEORIES DO NOT 
AUTOMATICALLY COME WITH ALGORITHMS ATTACHED -- THEY ARE DESCRIPTIONS OF 
NATURE, AND ONLY SECONDARILY DO THEY ALLOW ALGORITHMIC PREDICTION OF 
EXPERIMENTAL RESULTS.
 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).
 "BUILDING M AND LETTING IT RUN" IS *PRECISELY* THE POINT.  THE PHYSICAL 
THEORY WOULD TELL US THAT THE EXPERIMENT OF RUNNING M WILL PUT OUT A 
NONRECURSIVE SEQUENCE.  THE WHOLE POINT IS THAT YOU MUST DO THE EXPERIMENT, 
JUST CALCULATING FROM T+D ON A CLASSICAL COMPUTER WON'T DO IT.  FOR THIS TO 
MAKE SENSE THE SEQUENCE, WHILE NOT RECURSIVE, HAD BETTER BE MATHEMATICALLY 
DEFINABLE.
 It seems that issues of determinism are wrapped in here. >>
NO, THIS WORKS IN A DETERMINISTIC OR A NONDETERMINISTIC PHYSICAL THEORY -- IN 
THE NONDETERMINISTIC THEORY YOU CAN ONLY OBTAIN THE NONRECURSIVE SEQUENCE 
WITH ARBITRARILY HIGH PROBABILITY RATHER THAN WITH CERTAINTY, BUT THAT STILL 
COUNTS AS A VIOLATION OF THE CHURCH-TURING THESIS.  

FOR ANY DEFINABLE-BUT-NOT-RECURSIVE SEQUENCE a1,a2,a3,... THERE IS A FINITE 
INDEX N SUCH THAT ZFC DOES NOT DECIDE THE VALUE OF a_n; SO WE DON'T NEED 
INFINITE PRECISION, AT SOME FINITE TIME WE WILL ALREADY HAVE OBTAINED A NEW 
MATHEMATICAL FACT INDEPENDENT OF ZFC (BUT FOLLOWING FROM ZFC+T).  THIS WOULD 
DEMONSTRATE THAT MATHEMATICS IS NOT LOGICALLY PRIOR TO PHYSICS.

-- Joe Shipman