[FOM] Reply to Smith on Universality
joeshipman at aol.com
Sun Nov 4 18:00:29 EST 2007
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
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
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 * #
(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
Email and AIM finally together. You've gotta check out free AOL Mail! -
More information about the FOM