[FOM] Reply to Smith on Universality

[joeshipman@aol.com]

Alexander Smith's long post on the differing definitions of 
Universality clarifies many things, but it seems to me that relatively 
little is gained by using very complex definitons of Universality in 
order to show that ever smaller Turing Machines are "Universal".

Let's instead take a simple and robust defintion of Turing Machine 
Universality, that the set of finite inputs (input tapes where all but 
finitely many squares are blank) for which the TM halts is r.e. 
complete. The following modifications to this definition appear 
harmless:

1) instead of a special halt state (which does not count for purposes 
of measuring how many states the TM has), define halting as what 
happens when there is no quintuple with a state-symbol pair 
corresponding to the current state and currently scanned symbol.

2) Allow the initial tape configuration to have infinitely many 
non-blank squares, as long as the pattern is eventually periodic in 
both directions (not necessarily the same periodic pattern on the left 
and on the right).

3) Allow a subset S of input tapes where the machine halts to be r.e. 
complete, rather than the set of all input tapes where the machine 
halts, as long as S is recognizable by a finite automaton started on 
the "halt square" of the final tape configuration.

4) Allow allow a superset S of input tapes where the machine halts to 
be r.e. complete, rather than the set of all input tapes where the 
machine halts, as long as the non-halting elements of S can be defined 
in terms of finitely many "walks", where a "walk" is a situation where 
the TM cycles infinitely through a periodic sequence of states and 
scanned symbols.

The reason I call these modifications "harmless" is that it is obvious 
how to transform a "Universal" TM according to one of the modifications 
into a TM that is "Universal" according to the original definition, 
with only a small increase in "size" as defined by (# of quintuples), 
or a somewhat larger increase in "size" as defined by (# of states * # 
of symbols).

(I think "# of quintuples" is a much better measure than state-symbol 
product for this reason as well as because it is not clear one should 
be indifferent between m states-n symbols and n states-m symbols).

I believe that there is a lot of room for improvement in finding the 
smallest TM universal under my definition, and that finding the 
smallest TM universal under a definition modified as I outlined above 
would be less controversial  than finding the smallest TM under Smith's 
definition, which was formulated AFTER the Wolfram contest was 
announced (it is unsatisfactory to have the result of the contest 
depend on opinions of judges about the suitability of a definition, it 
should depend only on the opinions of judges about the validity of a 
formal result).

-- JS
________________________________________________________________________
Email and AIM finally together. You've gotta check out free AOL Mail! - 
http://mail.aol.com