[FOM] Directions for Computability Theory Beyond the PureMathematical

Wed May 17 11:32:40 EDT 2006

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 