The dominance of PG over PE 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
2logl(x) + 2logl(y) + l(xy) + O(1) bits). The
PEOM uses dovetailing to run
all self-delimiting programs on the y-th EOM of an enumeration of all
EOMs, to approximate the probability PEOM(y,x) (again encoded as a string)
that the EOM's output
starts with x. PEOM(y,x) is approximable (we may
apply Theorem 5.5) but
not necessarily enumerable. On the other hand, it is easy to see that
PEOMs can compute all enumerable strings describable on EOMs. In this
sense PEOMs are more expressive than EOMs, yet never diverge like GTMs.
EOMs can encode some enumerable 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 enumerable functions
of enumerable strings.