[FOM] Directions for Computability Theory Beyond the PureMathematical

Wed May 17 14:03:53 EDT 2006

Okay, I think there are two questions here

1) Is their a sequence of events in the world (coded up as a real number and
chosen in some 'computable' fashion) which is non-computable.

2) Are the underlying laws of nature computable (laws viewed as a function
predicting what happens in the future).

I was arguing that we can't experimentally distingush between a positive
answer to 2 which postulates fundamentally random events from a negative
answer to 2 which doesn't.  Thus we can have no confidence that even
apparently computable laws such as QM which allow random events are really
computable because they could be  'hiding' all their non-computability in
the random events.

I realize now that you were asking 1 and not 2.  For 1 it is no longer
important to distinguish non-computable laws from genuine random events so
the problem I raised doesn't apply (they are both going to result in a yes
answer to 1).  Sorry for the confusion.

However, I'm skeptical that the process you name is the only way to get
evidence for a positive answer to 1.  Suppose we get lots of support for a
theory like QM which postulates random events.   This seems to be strong
indirect evidence for a yes answer to 1.  If we believe the theory and take
the events to be truly random then, since an infinite string of coin flips
is going to be non-computable with probability 1, we have reason to believe
that some non-computable sequence is produced by nature.

For example take some event QM says happens randomly with probability .5
(measuring an electron as being spin up in y axis given we have just
measured it's spin in the x-axis).  Now supposing we have good reason to
believe this event is going to happen infinitely many times then if QM is
correct we should believe with probability 1 that nature will produce a
non-computable real.

I'm not sure how convinced I am by this sort of argument.  However, if we
are going to accept this sort of indirect evidence for electrons shouldn't
we be willing to do it for non-computable reals in nature?

Peter

On 5/17/06, S. Spijkerman / F. Waaldijk <sufra at hetnet.nl> wrote:
>
> thanx peter for your reply.
>
> however i don't quite follow. actually, i was trying to point out the
> opposite it seems? perhaps i should make myself a bit clearer.
>
> i know of the discussion about determinism and quantum mechanics. however
> it
> strikes me that `determinism' in that context is not very sharply
> (mathematically) defined. and the subject of determinism seems a little
> heated too...
>
> but if we put aside any philosophical considerations, a very simple and
> natural question about the physical world is this:
>
> is nature capable of producing a non-computable (non-recursive) real
> number?
>
> now the idea that i mentioned is to forget about any theory, and simply
> perform a very blunt and direct numerical physical experiment. like i
> said,
> take a fluctuating real from a physical measurement such as atmospheric
> pressure or the like. and simply wait to see whether this real for some m
> falls into an interval S_40,m . if for some m it does, well, i'm sorry but
> then scientifically speaking i see no more basis to accept the belief that
> nature is capable of producing non-computable sequences.
>
> this would in my opinion cast a very different light on the relation
> between
> recursive mathematics and classical mathematics. i mean, aren't we
> concerned
> with how accurately mathematics reflects reality?
>
> but perhaps i'm mistaken somewhere? therefore reactions are welcome!
>
> frank waaldijk
>
> ----- Original Message -----
> From: Peter Gerdes
> To: Foundations of Mathematics
> Sent: Monday, May 15, 2006 7:40 AM
> Subject: Re: [FOM] Directions for Computability Theory Beyond the
> PureMathematical
>
>
> 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
> wrong.
>
> 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.
>
> Peter
>
>
> 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
>
>

-- 
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/20060517/45c95331/attachment-0001.html