Abstract:
In 1975, Chaitin introduced his celebrated Omega number, the
halting probability of a universal Chaitin machine, a universal Turing machine
with a prefix-free domain. The Omega number’s bits are algorithmically
random—there is no reason the bits should be the way they are, if we define
“reason” to be a computable explanation smaller than the data itself. Since
that time, only two explicit universal Chaitin machines have been proposed,
both by Chaitin himself.
Concrete algorithmic information theory involves the study of particular
universal Turing machines, about which one can state theorems with specific
numerical bounds, rather than include terms like O(1). We present several
new tiny Chaitin machines (those with a prefix-free domain) suitable for the
study of concrete algorithmic information theory. One of the machines, which
we call Keraia, is a binary encoding of lambda calculus based on a curried
lambda operator. Source code is included in the appendices.
We also give an algorithm for restricting the domain of blank-endmarker
machines to a prefix-free domain over an alphabet that does not include the
endmarker; this allows one to take many universal Turing machines and construct
universal Chaitin machines from them.