[FOM] Directions for Computability Theory Beyond the Pure Mathematical

Peter Gerdes gerdes at math.berkeley.edu
Mon May 15 01:40:46 EDT 2006

Well this relates to something I have been thinking about for awhile.  I
don't think this point has been noted in the literature yet but I could be

Anyway code up the measurements from nature by a real number as you
suggest.  Now by well known facts there is a 1-random to which this real is
turing reducible.

Thus no matter how non-computable the actual world may end up being it will
always look computable but with some random events.  In other words if the
world is actually too complex to be predicted computably it will look like
just some purely random events plus a computable rule to derive observations
from these random events.

So unless we insist on a deterministic theory of the world (and QM is
already not deterministic) it doesn't seem there is any way to distinguish
true non-computability from randomness.

I've been vaguely toying with the idea of putting this together into a more
cogent form and writing it up as an argument against realism about
randomness in the sciences but haven't done anything with it yet.  If anyone
knows any references on the use of randomness (the computability notion) in
relation to scientific realism/induction I would love to hear about them.


On 5/14/06, S. Spijkerman / F. Waaldijk <sufra at hetnet.nl> wrote:
> perhaps you will allow me to introduce a related issue that i'm not sure
> about.
> i put it in my recent paper
> (
> http://home.hetnet.nl/~sufra/foundations%20of%20constructive%20mathematics.pdf
> ),
> but i haven't had any really interested responses yet.
> the issue is this:
> 1. we can construct (constructive!) coverings of the recursive interval
> [0,1] which have arbitrarily small classical measure (although they are
> not
> measurable constructively). in fact we can for any n give a countable
> sequence of intervals (S_n,m)_(m in N) such that the recursive interval
> [0,1] is covered by (S_n,m)_(m in N), and such that also constructively
> the
> sum of the lengths of the intervals (S_n,m)_(m in N) does not exceed
> 2^(-n).
> 2. taking every 10 seconds say a nontrivial measurement from nature (a
> fluctuating natural phenomenon) which in principle yields an infinite
> sequence \alpha, we can easily transform \alpha to be a decimal real
> number
> in [0,1].
> 3. letting H_0 be the hypothesis: `the real world is non-computable'
> (popularly speaking), and letting \beta be the uncertainty parameter of
> say
> 2^(-40) , we could start constructing (S_40,m)_(m in N).
> 4. it seems to me that if we ever discover an m such that \alpha is in
> S_40,m , then we have to discard H_0.
> this seems to me a legitimate scientific experiment, which can be actually
> carried out. of course, it is one-sided, but on the other hand any outcome
> would be spectacular i think?
> well, i hesitate but since it was printed already...go on and shoot...
> frank
> ----- Original Message -----
> From: "John Case" <case at mail.eecis.udel.edu>
> To: <fom at cs.nyu.edu>
> Cc: "John Case" <case at mail.eecis.udel.edu>
> Sent: Saturday, May 13, 2006 12:31 AM
> Subject: [FOM] Directions for Computability Theory Beyond the Pure
> Mathematical
> > Ted Slaman in [Long range goals, COMP-THY Archives, \#13, April 1998]
> > nicely mentioned the central theme of his intellectual motivation
> > (deriving from the influence of Sacks) for working in
> > Computability Theory (CT), a.k.a. Recursive Function Theory,
> > namely, definability.  There was also some call around that time
> > for posting new directions in CT.  I started to draft such a posting,
> but
> > didn't finish until yesterday.  When I was in Singapore January'06 and
> > talking with Sergey Goncharov also visiting there, he invited me to
> submit
> > a book chapter for [Mathematical Problems from Applied Logic.
> > New Logics for the XXIst Century II (edited by D. Gabbay, S. Goncharov,
> > and
> > M. Zakharyaschev), International Mathematical Series, Springer, to
> appear
> > 2006].   A draft of my intended book chapter, entitled,
> > Directions for Computability Theory Beyond Pure Mathematical, is,
> > currently,
> > available from http://www.cis.udel.edu/~case/papers/rft-directions.pdf
> >
> > (-8 John
> >
> > John Case                              Email: case at cis.udel.edu
> > Professor                              Phone: +1-302-831-2714
> > Computer and Information Sciences Dept. 101A Smith Hall
> > FAX: +1-302-831-8458
> > University of Delaware Newark, DE 19716-2586 (USA)             Home:
> > +1-302-836-4888
> >                URL:  http://www.cis.udel.edu/~case
> >
> >
> >
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom

Three passions, simple but overwhelmingly strong, have governed my life: the
longing for love, the search for knowledge, and unbearable pity for the
suffering of mankind.

--Bertrand Russell
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/fom/attachments/20060515/03e64ff2/attachment.html

More information about the FOM mailing list