Abstract:
Abstract. The present work clarifies the relation between domains of universal
machines and r.e. prefix-free supersets of such sets. One such characterisation can
be obtained in terms of the spectrum function sW(n) mapping n to the number
of all strings of length n in the set W. An r.e. prefix-free set W is the superset
of the domain of a universal machine iff there are two constants c, d such that
sW(n) + sW(n + 1) + . . . + sW(n + c) is between 2n−H(n)−d and 2n−H(n)+d for all
n; W is the domain of a universal machine iff there is a constant c such that for each
n the pair of n and sW(n) + sW(n + 1) + . . . + sW(n + c) has at least the prefix-free
description complexity n. There exists a prefix-free r.e. superset W of a domain of a
universal machine which is the not a domain of a universal machine; still, the halting
probability ΩW of such a set W is Martin-Löf random. Furthermore, it is investigated
to which extend this results can be transferred to plain universal machines.