Das Kalenderblatt 111029

28/10/2011 - 10:16 von WM | Report spam
Das Kalenderblatt 111029


Where does the halting probability come from? [...]
Formally, the halting probability Omega is defined as follows:

0 < Omega = SUM[program p halts] 2^-(the size in bits of p) < 1

To avoid having this sum diverge to infinity instead of converging to
a number
between zero and one, it is important that the programs p should be
self-delimiting (no extension of a valid program is a valid program;
see [Chaitin [2005]).
What's interesting about Omega is that it behaves like a compressed
version of Borel's know-it-all real {{s. KB112023}}. Knowing the first
n bits of Borel's real enables us to answer the first n yes/no
questions in French. Knowing the first n bits of Omega enables us to
answer the halting problem for all programs p up to n bits in size.
I.e., n bits of Omega tells us whether or not each p up to n bits in
size ever halts. (Can you see how?) That's a lot of information!
{{Hier übertreibt Chaitin ein wenig. Es geht, wie oben gesagt, um die /
Wahrscheinlichkeit/, dass ein Programm hàlt. Außerdem besteht eine
Codierungsabhàngigkeit, so dass Omega keine eindeutig definierte
Konstante ist.}}
In fact, Omega compactly encodes so much information that you
essentially need an n-bit FAMT in order to be able to determine n bits
of Omega! In other words, Omega is irreducible mathematical
information, it's a place where reasoning is completely impotent. The
bits of Omega are mathematical facts that can be proved, but
essentially only by adding them one by one as new axioms! I'm talking
about how difficult it is to prove theorems such as

"the 5th bit of Omega is a 0"
and
"the 9th bit of Omega is a 1"

or whatever the case may be.
To prove that Omega is computationally and therefore logically
irreducible, requires a theory of program-size complexity that I call
algorithmic information theory (AIT) [Chaitin, 2005]. The key idea in
AIT is to measure the complexity of something via the size in bits of
the smallest program for calculating it. This is a more refined
version of Borel's idea [Borel, 1960] of defining the complexity of a
real number to be the number of words required to name it.
And the key fact that is proved in AIT about Omega is that

H(Omega_n) >= n - c.

I.e., (the string Omega_n consisting of the first n bits of Omega) has
program-size complexity or "algorithmic entropy H" greater than or
equal to n - c. Here c is a constant, and I'm talking about the size
in bits of self-delimiting programs.
In other words, any self-delimiting program for computing the first
n bits of Omega will have to be at least n - c bits long.
The irreducible sequence of bits of Omega is a place where
mathematical truth
has absolutely no pattern or structure that we will ever be able to
detect. It's a place where mathematical truth has maximum possible
entropy - a place where, in a sense, God plays dice.
Why should we believe in real numbers, if most of them are
uncomputable?
Why should we believe in real numbers, if most of them, it turns out,
are maximally unknowable like Omega?

Note: In spite of the fact that most individual real numbers will
forever escape us, the notion of an arbitrary real has beautiful
mathematical properties and is a concept that helps us to organize and
understand the real world. {{Nein. Dazu könnte keine einzige
unzugàngliche "reelle" Zahl beitragen.}} Individual concepts in a
theory do not need to have concrete meaning on their own; it is enough
if the theory as a whole can be compared with the results of
experiments. {{Dann machen wir doch einmal das Experiment, aus der
Menge der unzugànglichen "reellen" Zahlen eine erste auszuwàhlen.}}

Borel, E. [1960] Space and Time (Dover, Mineola) pp. 212{214.
Chaitin, G. [2005] Meta Math! (Pantheon, New York).

[Gregory Chaitin: "How real are real numbers?" (2004)]
http://arxiv.org/abs/math.HO/0411418

Gruß, WM
 

Lesen sie die antworten

#1 Carsten Schultz
28/10/2011 - 14:12 | Warnen spam
Am 28.10.11 10:16, schrieb WM:
Individual concepts in a
theory do not need to have concrete meaning on their own; it is enough
if the theory as a whole can be compared with the results of
experiments.



Genau das ist der Punkt, den Du nicht verstehst.

{{Dann machen wir doch einmal das Experiment, aus der
Menge der unzugànglichen "reellen" Zahlen eine erste auszuwàhlen.}}



Und hier zeigst Du das einmal mehr.

Carsten Schultz (2:38, 33:47)
http://carsten.codimi.de/
PGP/GPG key on the pgp.net key servers,
fingerprint on my home page.

Ähnliche fragen