The dominance of
over
comes at
the expense of occasionally ``unreasonable,'' nonconverging outputs.
Are there classes of always converging TMs more expressive than EOMs?
Consider a TM called a
PEOM whose inputs are pairs of finite bitstrings
(code
them using
bits). The
PEOM uses dovetailing to run
all self-delimiting programs on the
-th EOM of an enumeration of all
EOMs, to approximate the probability
(again encoded as a string)
that the EOM's output
starts with
.
is approximable (we may
apply Theorem 5.5) but
not necessarily c.e. On the other hand, it is easy to see that
PEOMs can compute all c.e. strings describable on EOMs. In this
sense PEOMs are more expressive than EOMs, yet never diverge like GTMs.
EOMs can encode some c.e. strings slightly more compactly, however,
due to the PEOM's possibly unnecessarily bit-consuming input encoding.
An interesting topic of future research may be to establish a
partially ordered expressiveness hierarchy among classes of always
converging TMs, and to characterize its top, if there is one, which we doubt.
Candidates to consider may include TMs
that approximate certain recursive or c.e. functions
of c.e. strings.