Small Universal TMs

[JOSEPH SHIPMAN]

Check the FOM archives for October and November 2007!

https://cs.nyu.edu/pipermail/fom/

— JS

Sent from my iPhone

> On Mar 6, 2021, at 10:00 PM, Deutsch, Harry <hdeutsch at ilstu.edu> wrote:
> 
> I think if there is going to be discussion of this issue there should be some background provided, in particular concerning Smith’s result and Shipman’s other terminology. HD
> 
> Sent from my iPad
> 
>> On Mar 6, 2021, at 5:25 PM, JOSEPH SHIPMAN <joeshipman at aol.com> wrote:
>> 
>> [This message came from an external source. If suspicious, report to abuse at ilstu.edu<mailto:abuse at ilstu.edu>]
>> 
>> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20210306/c285281d/attachment-0001.html>