Small Universal TMs

[JOSEPH SHIPMAN]

There was a lot of discussion about small universal TMs in 2007, following Wolfram’s announcement of Smith’s discovery of a “Universal” 2-state 3-symbol UTM which required not only a non-blank input tape, but a non-periodic one, and a machine that did not “halt” but merely did something obviously terminal (such as repeating a previous configuration except with a repetitive element of the tape on each end extended and an increasingly large central segment traversed unmodified).

I care about the total amount of information to specify the system, so I think it’s cheating to put an arbitrary amount of complexity into the initial tape. But I can propose a new measure: you have two TMs, one which starts from blank tape and finishes with the complex input tape for the second, which has a distinguished location from which the “input” for the UTM commences. I’m also willing to allow a complex “halt” state only if the initial tape is eventually periodic (possibly differently left and right) and the “halt” consists of a simple periodic shift-insertion (there are two configurations differing only by an insertion of a segment in a region of the tape unvisited between the two).
Then the “score” is the sum of the number of quintuples in each machine (no restriction on number of symbols, an absent state-symbol pair in the program triggers a halt).

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.

— JS

Sent from my iPhone