FOM: Reply to Pratt

Vaughan R. Pratt pratt at cs.Stanford.EDU
Tue Nov 4 18:43:27 EST 1997

>Church's thesis says that any sequence of bits we can
>effectively generate is recursive. 

Church's thesis says that all effective procedures have a common upper
bound on what they can do.  The word "recursive" does not appear by
itself in the characterization of that upper bound, it is either
"recursively enumerable" or "partial recursive" depending on whether
applied to sets or functions.

>If Chaitin's r.e.-complete number omega were experimentally available
>(e.g. as a probability) it would thus provide a source of new
>theorems.  The "new axiom" would be that the physical theory involved
>was correct. -- Joe Shipman

This is covered under scenario 2 of my previous message, where some
theory has predicted that this infinite amount of information is
present (as the infinite precision real number omega in this case), and
empirically the theory has been tested and never found to be wrong, and
found to be right in convincingly many cases (with many more
predictions remaining necessarily forever untested).  My point there
was that accepting such an empirically confirmed "axiom" is what
experimentalists routinely do.  It's not however what mathematicians
have ever done in a theory intended for actual use (as opposed say to
the non-r.e. set of all arithmetic truths as axioms), where the axioms
are always presented as, if not singletons, at most primitive recursive
sets of formulas.


More information about the FOM mailing list