Randomness and Mathematical Proof

[Paola Di Maio <paola.dimaio@xxxxxxxxx>]

Came across this paper by Chaitin

Randomness and Mathematical Proof

Scientific American 232, No. 5 (May 1975), pp. 47-52

by Gregory J. Chaitin

Although randomness can be precisely defined and can even be measured,
a given number cannot be proved to be random.  This enigma establishes
a limit to what is possible in mathematics.


http://www.cs.auckland.ac.nz/~chaitin/sciamer.html

it references Solomonov

clever work eh?

P

On Sat, Jan 23, 2010 at 5:38 PM, Rich Cooper <rich@xxxxxxxxxxxxxxxxxxxxxx> wrote:

John and Rob,

This would be a good moment to credit Solomonov and Kolmogorov, who also
addressed the issue of irreducibility, but of data rather than process.
Since data and process work together, they are different aspects of the same
duality.

JMHO,
-Rich

Sincerely,
Rich Cooper
EnglishLogicKernel.com
Rich AT EnglishLogicKernel DOT com

-----Original Message-----
From: ontolog-forum-bounces@xxxxxxxxxxxxxxxx
[mailto:ontolog-forum-bounces@xxxxxxxxxxxxxxxx] On Behalf Of John F. Sowa
Sent: Saturday, January 23, 2010 9:34 AM
To: edbark@xxxxxxxx; [ontolog-forum]
Subject: Re: [ontolog-forum] rant on pseudoscience

Rob and Ed,

JFS>>>> First of all, it is essential to distinguish empirical sciences
 >>>> from pure mathematics.  In empirical sciences, the ultimate test
 >>>> is agreement of predictions with observations.  Mathematics,
 >>>> however, is not an empirical science.

RF>>> Greg Chaitin might have issue with that statement.

JFS>> No. He wouldn't object to that statement.

RF> You can choose to speculate that way if you wish.
 >
 > I suggest anyone interested read Chaitin in the original. He is
 > a very enjoyable read.

I have read many of Chaitin's publications, and I agree that he has
a talent for making complex discussions enjoyable.  But he never
confuses mathematical issues with claims about the physical world.
He was careful to use the term 'quasi-empirical', not 'empirical'.

EB> One of my professors once commented that there is an empirical
 > branch of mathematics -- number theory.  It must be empirical,
 > said he, because no result generalizes.  :-)

I'm happy that you followed that statement with a happy face --
because I suspect that's what your professor intended.  Greg C.
added the prefix 'quasi-' to distinguish that aspect of math
from empirical statements about the physical world.

What Chaitin called quasi-empirical is closely related to what
Wolfram called computationally irreducible.  Following is a note
I wrote in a different thread.

John
__________________________________________________________________

Don't attribute claims to Wolfram that come from Wikipedia:

RF> Or you could look at Stephen Wolfram's idea of "computational
irreducibility". It appears to me to be saying the same thing:
 >>
 >> "The empirical fact is that the world of simple programs contains a
 >> great diversity of behavior, but, because of undecidability, it is
 >> impossible to predict what they will do before essentially running
 >> them. The idea demonstrates that there are occurrences where theory's
 >> predictions are effectively not possible."
 >>
 >> http://en.wikipedia.org/wiki/Computational_irreducibility

CM> Yes, although he appears to be citing undecidability to illustrate
 > a more general claim about the predictive limitations of theories.

I agree that statement is confused.  But it comes from Wikipedia.
Wolfram himself is more nuanced.  See

http://www.wolframscience.com/nksonline/page-737

For example, Wolfram says (p. 741)

SW> [Computational irreducibility implies] that for many systems
 > no systematic prediction can be done, so that there is no
 > general way to shortcut their process of evolution, and as
 > a result their behavior must be considered computationally
 > irreducible.

In other words, Wolfram is saying that the amount of computation
needed to predict what the system will do may be extremely large,
but finite.  In fact, it may take the same amount of time that
is required to simulate the system.

Undecidability implies that *no* finite amount of computation
can make the prediction.


_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx



_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx

-- 
Paola Di Maio
**************************************************
“Logic will get you from A to B. Imagination will take you everywhere.”
Albert Einstein
**************************************************

_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/  
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/  
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/ 
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx    (01)