Complexity of UTM'S

[Ignacio Añón]

Shipman wrote:

"So: what’s the current best known

classical UTM (blank initial tape, true halt)?
looping UTM (blank initial tape, periodic shift-insertion regarded as halt)?
“double UTM” (one writes the tape, the other has a true halt state)?
“double looping UTM” (one writes the tape eventually-periodically, the
other can have periodic shift-insertion halting)?

Unfortunately, Alexander Smith’s “(2,3)” UTM won’t count, because its
input tape was not eventually periodic and therefore its halting
condition was more complex than noticing a simple shift-insertion.

The only additional type of pseudo-halt I would be willing to consider
is one with alternating left and right shift-insertions, but you might
then need to get a bit tricky about what it can do in the middle."

These limit problems are quite interesting, but they all seem to fall
under the relative entropy questions that are "minimally" grasped by
the notion of strong sub-aditivity, which sets an optimal bound, to
the entropy of any system in information theory: UTM's are just
trivial examples of such systems.

Complexity theory, in the style of Karatsuba, is the state of the art
treatment of these problems, it seems to me. His work also suggests a
fascinating type of elementary, natural, number theoretic problem,
that is consistent with the "Minimal" Cohen model of ZFC, but
independent of it...