How (not) to Compute the Halting Probability or Validate the Heuristic Principle

Two important achievements of Chaitin will be discussed: the Omega number, which is claimed to be the halting probability of randomly given input-free programs, and the heuristic principle, which is claimed to hold for program-size complexity. Chaitin's heuristic principle says that the theories cannot prove the heavier sentences; the sentences and the theories were supposedly weighed by various computational complexities, which all turned out to be wrong or incomplete. In this talk, we will introduce a weighting that is not based on any computational complexity but on the provability power of the theories, for which Chaitin's heuristic principle holds true. We will also show that the Omega number is not the claimed probability of halting (the randomly given input-free programs). We will investigate the mathematical result that is guilty of this fallacy: the Kraft-McMillan inequality.