Between EOMs and GTMs? next up previous contents
Next: Temporal Complexity Up: Probability vs Descriptive Complexity Previous: Tighter Bounds?

Between EOMs and GTMs?

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 $x,y \in B^*$ (code them using 2log l(x) + 2log l(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.


next up previous contents
Next: Temporal Complexity Up: Probability vs Descriptive Complexity Previous: Tighter Bounds?
Juergen Schmidhuber
2001-01-09


Related links: In the beginning was the code! - Zuse's thesis - Life, the universe, and everything - Generalized Algorithmic Information - Speed Prior - The New AI