Abstract:
This thesis examines some problems related to Chaitin’s
number. In the first section, we describe
several new minimalist prefix-free machines suitable for the study of concrete algorithmic information
theory; the halting probabilities of these machines are all
numbers. In the second part, we show that
when such a sequence is the result given by a measurement of a system, the system itself can be shown
to satisfy an uncertainty principle equivalent to Heisenberg’s uncertainty principle. This uncertainty
principle also implies Chaitin’s strongest form of incompleteness.
In the last part, we show that
can be written as an infinite product over halting programs; that
there exists a “natural,” or base-free formulation that does not (directly) depend on the alphabet of
the universal prefix-free machine; that Tadaki’s generalized halting probability is well-defined even for
arbitrary univeral Turing machines and the plain complexity; and finally, that the natural generalized
halting probability can be written as an infinite product over primes and has the form of a zeta function
whose zeros encode halting information. We conclude with some speculation about physical systems in
which partial randomness could arise, and identify many open problems.