Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness.
type: Item
instance of: scholarly article
title: Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness.
zbMATH Open document ID: 1042.68045
DOI: 10.1016/S0304-3975(01)00068-8
author: Cristian S. Calude
published in: Theoretical Computer Science
publication date: 2002-07-31T00:00:00Z
review text: Computably enumerable (c.e.) reals can be coded by Chaitin machines through their halting probabilities. Tuning Solovay's construction of a Chaitin universal machine for which ZFC (if arithmetically sound) cannot determine any single bit of the binary expansion of its halting probability, we show that every c.e.~random real is the halting probability of a universal Chaitin machine for which ZFC cannot determine more than its initial block of 1 bits -- as soon as you get a 0, it is all over. Finally, a constructive version of Chaitin information-theoretic incompleteness theorem is proven.
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 1774164
zbMATH Keywords: Computably enumerable real
zbMATH Keywords: Chaitin machine
zbMATH Keywords: Random real
zbMATH Keywords: Information-theoretic incompleteness
Wikidata QID: Q57001702
MaRDI profile type: Publication
cites work: Q4326782
cites work: A characterization of c. e. random reals
cites work: Q4381402
cites work: Q4520520
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Algorithmic Information Theory
cites work: Information, randomness and incompleteness. Papers on algorithmic information theory
cites work: Q4942040
cites work: Q4259438
cites work: Presentations of computably enumerable reals.
cites work: Q4219053
cites work: Randomness and recursive enumerability
cites work: Classical recursion theory. The theory of functions and sets of natural numbers
cites work: Q4934359
description: scientific article; zbMATH DE number 1774164