Professor Cristian Calude from the University of Auckland gave a fascinating talk on “Incompleteness: A Personal Perspective” at Google a few weeks ago. Its available to a wider audience now:
A little study after the talk led to the discovery that Omega was not just this real number representing the halting probability of a random program on a Universal Turing Machine. But the reasoning used to derive the halting probability can be extended and if ZFC is arithmetically sound, Goldbach’s Conjecture and Reimann Hypothesis can be proved or disproved by computing Omega upto a certain length (The problem being the difficulty in computing it).
Dr. Cristian mentioned briefly about how Omega for Prefix Free Universal Turing Machines can be computed modulo certain limitations and his work in computing the first 64 bits for a specific machine. (And we are formally educated that Omega is incomputable !)
Incompleteness is as much a blessing as it is a curse. Let Automatic Theorem Provers take care of Predicate Calculus and boring First Order Logic. Humans can spend time in creative dreaming about the truth of the continuum hypothesis because we are not affected by Godel – we are Super-Turing calculators 
Filed under: Computer Science, Mathematics
Welcome back…..it is good to have you back and again………..
@aangtce:
Good to see you back too
How is Omega computable ???
There are infinite number of programs for TM. And infinite number of them can be halted.
So Omega = Infinity / Infinity. Even if only a finite set of programs are halted, Omega = Real / Infinity. How can it be computed ???
Any idea ???
@joerg:
Your reasoning is flawed. Simply because something is infinity doesn’t mean it is incomputable.
Exempli Gratia: The ratio of the cardinality of Even numbers (INFINITE) to the cardinality of Natural Numbers (INFINITE) is exactly 0.5
Duh ? Your presumption that computing the probability P(x) depends on the exhaustive enumeration of X is wrong. Sometimes its possible to compute probabilities simply by looking at the *structure* of the series.
The structure of Even numbers and Odd numbers turn out to be trivial. The structure of Prime Numbers is so complicated that we are tormented by Prime Counting and the Reimann-Zeta function.
In a similar vein: In the hyperspace of all Universal Turing Machines, certain machines expose their internal structure such that they are amenable to external systems calculating their halting probability Omega (albiet only upto a certain precision). While certain other machines are so bad that we cannot even compute the first bit of Omega.
Disclaimer: I have never studied any of this formally. This is merely my own way of explaining it and it might be completely bunkum.
@joerg:
I am wondering if your assertion about “an infinite number of programs for the UTM” is true. Remember that we are only talking about Omega for prefix-free Universal Turing machines. Given a finite set of input symbols on tape and enforcing a prefix-free encoding, are there really an *infinite* set of inputs to the UTM ?
An Infinite number of prefix-free codes could be *constructed*. But do all of them encode information theoretically significant data ?
I don’t know the answers – My imagination fails me whenever I do combinatorial math.
Welcome back from dormancy!
“The soul should always stand ajar, ready to welcome the ecstatic experience.” -Emily Dickenson. Those words explain how I feel to read your blog after a long time.
It was an interesting philosophy. I did not know about Omega until I read this blog. Here is the link to GJ Chaitin’s original work that gave rise to this Omega: http://www.umcs.maine.edu/~chaitin/acm75.pdf. I am not a fan of Immanual Kant. But as I read more about Omega, I think more of “Synthetic a-priori”. Is the occurance of prime, random or deterministic? OK, it’s time for me to sleep!
@ Sundar:
Interesting thought about Synthetic vs. Analytic statements.
Gottfried Leibniz once wrote “When a rule is very complex, Things that confirm to the rule appear random” – Prime Numbers, The Grand Unified Theory, Macro-Economics, Love …
Random comment on an old thread, I know, but I cannot help myself…
@Ananth: Great thinking and not wrong in spirit, but concerning your example – the even numbers and the natural numbers have the exact same cardinality, as demonstrated by Georg Cantor (since the members of each set can be put into a one-to-one relationship with the members of the other with none left out – like matching each finger on your right hand with a finger on your left). So if we are going to allow ourselves the luxury, the ratio would be 1 not 0.5. Now the ratio of the cardinality of the set of natural numbers to the set of all real numbers between 0 & 1 — those would have different cardinality…
Still, you are right. Calculations involving infinity are not ruled out categorically, at all. If they were, there would be no calculus, for which infinity is its bread and butter.
@ Wallace:
Thanks very much for sharing your insight – You are indeed right about the cardinality argument.
I had a barely superficial understanding of Aleph-0 when I wrote the post. My Set theory has progressed since then
Hi,
I still don’t follow why the ratio of cardinality of even numbers to that of natural numbers is one. Can you please help. I admit that my understanding of set theory and probability is very bad. I find other areas of Mathematics easier
@ bala:
I had to dive into Cantor, Set Theory and the Continuum Hypothesis when trying to read Turing’s 1936 paper – So I will write in detail about Enumerability sometime.
But to give a broad overview, Cantor proved that there are different classes of Infinity. Some sets are “more infinite” than others. For example real numbers are more infinite than natural numbers. But even numbers are only “as infinite as” natural or odd numbers since you can define a bijective relation between those sets.
There is no way to define a 1:1 mapping between real numbers and integers. And Cantor’s brilliant diagonalization argument proved that
Aleph_1 = (2 ^ Aleph_0)
Google away for more insight …
Hi,
Ok. I follow. I did a very basic study of Continuum hypothesis yesterday. Will try to dig more into. Thanks for the inputs