Abstract:
Using 1947 work of Post showing that the word problem for semigroups
is unsolvable, we explicitly exhibit an algebraic characterization
of the bits of the halting probability
Ω. Our proof closely follows
a 1978 formulation of Post’s work by M. Davis. The proof is selfcontained
and not very complicated.