What do you mean by the term “probability”? For example, how would you interpret the statement, “There is a 50% probability that this coin will come up heads”?
It’s context-dependent. As I said, there are at least two valid kinds of probability (a priori and a posteriori) and, with care, we can construct from these a third, more subtle form, which is the Bayesian probability (which has links to information theory and even to causal-reasoning).
The definition of the a priori probability of the outcome of a coin-flip is as follows: There are two faces of a coin, one of which must come up if the coin is flipped, and neither side is favored by the coin’s geometry, thus, the probability of a particular face coming up is 1 / 2 (possible outcomes). Note that this is a definition, not a proof or argument or an attempt to model the physics of a real coin-flip.
The definition of the a posteriori probability of the outcome of a coin flip is as follows: Flip it many times and count the number of times one side comes up and take the ratio of this to the total number of flips.
Clayton -
I mean for the purpose of interpreting the term “Omega.” A posteriori: probability is defined as the ratio of heads to tails in a number of coin flips performed. A priori: where’s the definition? But feel free to skip this; I’m just curious what definition of the term is used in defining the term Omega.
@AJ: OK, I’m not entirely sure what you’re asking but I’ll just explain how the probability Omega is defined.
Consider a Universal Turing Machine (UTM). It has an “input tape” which is just a series of 1’s and 0’s. We can imagine enumerating every possible input to the UTM machine as follows:
0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, …
Now, the hard part comes when you want to say, “Out of the set of all possible programs, choose one at random.” Isn’t the probability of a particular element of an infinite set precisely zero? Or, if you choose some other way to calculate the probability (such as counting the ones), you can end up with probability spaces all of whose elements sum to greater than 1.0 or even to infinity!
This is the first problem that Chaitin solved. He said, what if you attach a prefix to each program such that the prefix specifies the length of the program? Then you can simply assign a “weight” or “probability” to each such program based on the length of its prefix and we know from the properties of a prefix-free code (more commonly referred to as a prefix code) that any such code can be mapped to the probability space 0 to 1.
One such coding that is commonly used in algorithmic information theory is:
1L(x)0x
Where L(x) means “length of x in bits”. So, to encode the binary pattern 1101101:
For x = 1101101, L(1101101) = 7, so:
1701101101 = 111111101101101
The probability of every binary sequence can then be defined as 2-L(x). Thus, the probability of 1101101 is 2-7 = 1/128. If you take the sum of probabilities over all such codes, you will get 1.0 because Sum (k=1 to inf) 2-k = 1.0
We can also assign a physical meaning to this in terms of coin flips. Imagine a device:
Start: Counter=0; Flip a coin
1: If tails, go back to Start, else increment Counter and continue
2: Flip a coin; if heads, increment Counter and goto 2, else continue
3: Do the following Counter times: Flip a coin and report the result to the user
So, you can see that the probability of getting longer sequences is lower according to this configuration.
Now that we have some way to generate any given input program to our UTM, now it’s just a matter of asking “given a randomly chosen input to the UTM, what is the probability that it will halt?” That is Omega.
Clayton -
Since Omega is defined as the probability it will halt, I’m simply wondering what definition of the word “probability” is being used within that definition (a priori, a posteriori, etc. - and if a priori what is the actual definition?). As Andris mentioned, Chaitin’s conclusion seems to depend on probability being a non-subjective quantity, but Bayesians (at least Jaynes and Yudkowsky) say probability is subjective (which I assume means they define it in such a way that it is clearly a type of ignorance, etc.). So yeah, just a sentence as a definition of the term “probability” for the purpose of defining the word “Omega” is what I’m looking for.
@AJ: The ratio of halting programs to all programs - with the caveat that this is only meaningful if the set of all programs is structured as a prefix-code so some kind of measure can be placed on it. See the definition here. If every program halted, then the given sum would be 2-|p| over every p, which equals 1.0. So this definition satisfies the condition that a probability must lie between 0 and 1. I will direct your attention to this article for perhaps a more readable presentation of the argument against a mathematical ToE by Chaitin himself. Here’s another.
Clayton -
Oh I see, thanks. What do you think about Wildberger’s rejection of real numbers given Omega is supposed to be uncomputable? (Not to mention the infinities.)
Well, Omega is just a particular, incompressible real number. With probability 1, any real number is incompressible (maximally random), so Omega is not remarkable in that sense. What Omega helps explain is why real numbers in general don’t make sense… all but countably infinitely many real numbers (that is to say, with probability 1.0) are incompressible like Omega. The square-root of 2 or pi are counter-examples… real numbers that are not incompressible. But there are very few of these numbers. The rest are like Omega. So, what exactly do we need all these numbers that cannot - even in principle - be named or specified or picked out of a set? Somewhere Chaitin says “I do not think I believe in real numbers.”
If you want my opinion (and it is my opinion), two centuries from now, people will look back at the real number system like we look back at Roman numerals - how could anyone even do math at all with such a horrible numbering system??? I believe that the mischief comes from the fact that we have modeled our concepts of distance (measure) on the peculiar way we have constructed the decimal place-value system. The decimal place-value system was revolutionary and opened new vistas by comparison to the older systems that went before. But I’m of the opinion that we need to shift to thinking about math p-adically. This is not a question of the facts of math… those will remain the same either way. Rather, it is a question of how mathematicians are trained and the analytical structures within which human brains are thinking about mathematical problems. Our thoughts are the product in large part of the language we use. This is as true of mathematics as in the general case.
Clayton -
Oh my god, is there no end to anti-Establishment, guerilla philosophy and mathematics?? I just discovered Tau… the new alternative to pi, as in, the pi that you learned in school, the ratio of diameter to circumference. The Elites have been lying to us for thousands of years!
We’re on to you, Elites! Muahahahahahaha!!!
Clayton -
Via Aristippus: Problems in the Medieval chronology.
Clayton -
This is kind of a late response but I noticed you guys were talking about two’s complement.
I wanted to note that the two’s complement representation of -1, for example the 8-bit quantity 11111111b, can be extended infinitely to the left so that it is arguably a mathematically acceptable representation of -1, and not just a convenient computer trick:
Let s = …11111xb = 1 + 2 + 4 + 8 + 16 + …
Then
2s = 2 + 4 + 8 + 16 + … = s - 1
After subtracting s from each side you can conclude that s = -1.
Switching to decimal, you can likewise show that
…11111 = 1 + 10 + 100 + 1000 + … = 1/(1-10) = -1/9 and
…11111.1111… = -1/9 + 1/9 = 0
Euler used the harmonic series (h = 1 + 1/2 + 1/3 + 1/4 + …) to evaluate the convergent sum:
1/3 + 1/7 + 1/8 + 1/15 + 1/24 + 1/26 + … = 1 (here, each denominator is one less than a power)
And one of my favorite works is here http://www.math.dartmouth.edu/~euler/pages/E247.html
where he computes 1-1+2-6+24-120+720-… (alternating factorials) and ends up with the Gompertz constant (0.596…). IIRC he computes the sum six different ways - like through differential equations, integration, continued fractions, series acceleration, or computing the logarithm of the sum - getting the same result each time.
Euler also computed a number of sums such as
1 + 2 + 3 + 4 + 5 +… = -1/12 and
1^3 + 2^3 + 3^3 + … = 1/120
1^5 + 2^5 + 3^5 + … = -1/252
which led to his conjecture of the functional equation (reflection formula) of the so-called Riemann zeta function
There are also interesting products like
1 x 2 x 3 x 4 x… = sqrt(2pi) (If I remember correctly… I can derive it if you wish)
2 x 3 x 5 x 7 x 11 x … = (2pi)^2 (see http://mathworld.wolfram.com/PrimeProducts.html)
Simply admitting that negative numbers can in a sense be larger than infinity leads to techniques that are a lot more fun, and practically more useful, then the pedantic modern equivalents (“Borel summation”).
The p-adic valuation leads also to the same conclusions, at least in respect to the summations. It is clear to me that p-adic numbers are in some sense more “fundamental” than the real numbers.
In fact, I see a connection to information theory in the p-adic numbers. The negative of the log (base p) of the valuation of a p-adic number is also the number of “digits” in its p-adic representation. This suggests that the geometry of the p-adic numbers is the geometry of causality*.
Further illumination comes from investigating the finite truncated -adics, as in 2-adic used in computers today (two’s-complement binary). If you look at the 3-bit two’s complement numbers:
000 → 0
001 → 1
010 → 2
011-> 3
100 → -4
101 → -3
110 → -2
111 → -1
Adding these numbers together forms a modulo “ring”**. You can envision a circle with each of the eight binary values arranged around it… and addition/subtraction (which is really just addition) is just the direction you are going around the circle. Extending to ever larger bit-widths, we can see that the radius of the circle is increasing, or the density of the numbers around the circle is increasing, or both, however you choose to think about it. In the limit then, it is a “circle with infinite radius”, which, by the way, is a lot like this.
Euler’s sums and products are definitely among the most remarkable facts in mathematics and I think they are telling us something very fundamental about the nature of numbers.
A project I work on in my spare time at times: Is there a way to encode complex numbers that is as natural as the p-adic encoding of negative and fractional numbers?
Clayton -
- Information theory is linked to causality through the idea of dependent-variables… if you make a copy of classical information, this is a lot like quantum “entanglement” in that the copied information and the original information are not independent variables and, thus, their information content is no longer simply additive.
**I’m using ring in the non-mathematical sense of the word… a circle
Clayton: It is clear to me that p-adic numbers are in some sense more “fundamental” than the real numbers.
Hmmm… I’ve never really thought about it before, but real numbers do bother me since any given real number may require an infinite amount of information to define. In fact, this is true for all but an infinitesimal proportion of the real numbers.
Transcendental numbers that appear in practice can be defined by patterns like
pi = 3 + 1/(6+9/(6+25/(6+49/(6+…
log 2 = 1 - 1/2 + 1/3 - 1/4 + … = (pi / 4) / arithmetic-geometric-mean( (1 + 20.5^4 + 20.5^16 + 20.5^36 +…)^2,(20.5+20.5^9 +20.5^25+…)^2)
Algebraic numbers like the golden ratio can always be defined by continued fractions like 1+1/(1+1/(1+…
But I’ve never seen someone deal with a particular number that takes an infinite amount of information to represent.
Here’s an example of one: Chaitin’s constant. But as Chaitin himself constantly likes to point out, this number proves way too much about the real numbers, that is, it shows that the idea of “the real number set” simply doesn’t make sense. No finite axiomatic system can possibly deal with such a set.
Clayton -
I disagree Clayton. Chaitin’s constant only requires a finite amount of information to define. Otherwise a definition couldn’t even be given. It is not like most real numbers which require an infinite amount of information to specify (e.g. an endless Cauchy sequence of arbitrary numbers).
@baxter: Think again. While Omega has a definite value, even its definition (algorithm to compute it) requires infinite information. It is irreducible. And this is, in fact, the case for all reals but an infinitesimal fraction of them.
Clayton -
And you might object that Omega might be really hard to compute, but perhaps it’s not so hard to check (ala NP problems). But this is not the case… to check a candidate computation of Omega is just as hard as to compute Omega to begin with. So, while it is the case that the halting probability is the sum that Chaitin provides, that sum is merely formal, it could be applied to the probability of any language (Omega can be thought of as the weighted probability of the language HALTS), so it is not really a definition.
Clayton -
This is precisely the “property” (or lack of one) that Omega was constructed to have! It is a very odd number in that we can say there is some one, definite Omega (relative to a given computer), but at the same time, it’s in a kind of fuzzy superposition where the values of its bits are truly random, a “property” it shares with almost all other real numbers.
Clayton -
While Omega has a definite value, even its definition (algorithm to compute it) requires infinite information. It is irreducible.
I still don’t see things this way.
Omega is reducible: the infinite digits of omega can be conceptually compressed back into the very definition whence it came.
There is a trivial algorithm to approximate Omega that gets closer and closer the longer you run it. Each time a binary digit of Omega is determined, the set of possible values in which Omega is known to lie has its measure cut in half. Omega is only said to be “not computable” in the sense that the digits don’t arrive in a certain, pleasant order.
I think my main problem is that I feel some commonplace words are being abused in formal mathematics to make things sound mystical.
Nope, the words are being used to mean exactly what they mean.
“X is Uncomputable” means: no algorithm* computes X in computable time. Of course, it is trivial to write a definition that is “Search all possibilities and HALT when you’ve found the solution.” In thise sense, we can compute the Riemann Hypothesis or any unsolved mathematical problem. However, the heart of the issue is “how long would it take to search all possibilities and find the solution, and is there a faster (computable) way?” If you can prove that any algorithm that would solve a problem (given unlimited time) solves it more slowly than any computable function, you have proved that the problem is uncomputable.
The only “stronger” sense of uncomputable would be a contradiction (completely impossible).
Any finite algorithm that produces the bits of Omega must produce them more slowly than any computable function. Stated differently, it takes as long to solve the busy-beaver problem as it does to produce the bits of Omega.
Clayton -
*By definition, an algorithm must be of finite size