Some have dismissed this as old news from Godel, or a trivial result of
plucking randomness out of randomness. They are mistaken.
It is not about existence of undecidable statements, which would be old
news. Rather it is a construction of a true random number in mathematics
with the help of Turing's halting theorem.
There is a vast difference bewteen random statement and statement of
randomness. Let x be the result of the next toss of a coin. Consider the
statement
x = H.
Its truth is random. Now instead of individual events, we talk about the
probability of the events. Consider the statement
P(x = H) = 0.5.
This is not random at all. Furthermore, within the realm of probability
theory, we can construct a lot of compound statements which is either true
or false. Consider the statement that a particular hand in a card game has
a certain probability, for example.
Pause for a moment and think: suppose you always speak about probabilities,
never about specific events, can you construct a statement whose truth value
is random? Pretty hard, itsn't it? In a sense, Kolmogorov's zero-one
theorems state that the majority of statements well defined in his formal
system of probability is either true or false.
Now here comes the intriguing part. The Chaiting number is not dependent on
a random event (such as choosing a Turing machine). It is a probabability
(such as the proportion of Turing machines that halt). Yet it is still
random!
How could this be possible? The trick is that its definition relies on the
halting of Turing machines, which is not decidable within the system.
To summarize: Undecidable construction of known probabilities can produce a
random probability. That is, he is plucking randomness out of undecideness.
Interesting thought: Maybe randomness should be defined as undecidability?
Slashdot Mirror
It is not about existence of undecidable statements, which would be old news. Rather it is a construction of a true random number in mathematics with the help of Turing's halting theorem.
There is a vast difference bewteen random statement and statement of randomness. Let x be the result of the next toss of a coin. Consider the statement
x = H.
Its truth is random. Now instead of individual events, we talk about the probability of the events. Consider the statement
P(x = H) = 0.5.
This is not random at all. Furthermore, within the realm of probability theory, we can construct a lot of compound statements which is either true or false. Consider the statement that a particular hand in a card game has a certain probability, for example.
Pause for a moment and think: suppose you always speak about probabilities, never about specific events, can you construct a statement whose truth value is random? Pretty hard, itsn't it? In a sense, Kolmogorov's zero-one theorems state that the majority of statements well defined in his formal system of probability is either true or false.
Now here comes the intriguing part. The Chaiting number is not dependent on a random event (such as choosing a Turing machine). It is a probabability (such as the proportion of Turing machines that halt). Yet it is still random!
How could this be possible? The trick is that its definition relies on the halting of Turing machines, which is not decidable within the system.
To summarize: Undecidable construction of known probabilities can produce a random probability. That is, he is plucking randomness out of undecideness.
Interesting thought: Maybe randomness should be defined as undecidability?