next up previous
Next: Consequences for Physics Up: Probability vs Descriptive Complexity Previous: Tighter Bounds?

Between EOMs and GTMs?

The dominance of $P^G$ over $P^E$ 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 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.


next up previous
Next: Consequences for Physics Up: Probability vs Descriptive Complexity Previous: Tighter Bounds?
Juergen Schmidhuber 2003-02-13