[FOM] Simple Turing machines, Universality, Encodings, etc.

[Vaughan Pratt]

The following was originally in private reply to a message Alex Smith
sent me cc'ing Stephen Wolfram and Todd Rowland, whom I cc'd likewise in
my reply.  Now that Alex has in the meantime subscribed to FOM and
posted his message there, I'll follow suit (i.e. both Alex and I have 
sent our messages twice, once to each other and once to FOM).  --Vaughan

=========

To: Alexander Smith <AIS523 at bham.ac.uk>
CC: s.wolfram at wolfram.com,  rowland at wolfram.com

Dear Alex,

Pleased to make your acquaintance, if only electronically.  I appreciate
the opportunity to go over your proof with you directly rather than the
more complicated approach of going through intermediaries.

If your argument is correct then it is a very impressive piece of work
and you deserve both the prize and the fame that goes with it.  In
either case it is clear that you enjoy the challenge of difficult
problems and I hope that whatever the outcome you will be encouraged to
attack other problems with equal enthusiasm.  Many who've been rebuffed
by one problem have bounced back to successfully solve others and make
their reputation in due course, the occasional failure notwithstanding.
(And some have perfect track records perhaps, but those are very rare
indeed---certainly not me!)

I should also add, please don't take my question about how your proof
"got through the filter" as directed at you.  It is the judges'
responsibility to make the determination of correctness.  Ideally your
proof will turn out to be correct, but if as I argue below it is not
then you will have made an error but this often happens.  This
particular error while elementary is sufficiently subtle as to often
trip people up the first time they encounter it.  It is a much bigger
fault when the judges of such a competition fail to catch this sort of
well-known fallacy, and this was the basis for my opening question in my
post.

In the case of two PDAs, which was the first thought I had when I saw
your argument, I haven't considered whether the requirement that the
communication between the two machines be one-way and off-line (i.e.
performed at the start) is sufficient to inhibit universality, though it
seems plausible to me that this is the case (but then it would need to
be proved).

> For instance, a universal machine can search for counterexamples to 
> the Riemann hypothesis; the linear-bounded-automata+preprocessor 
> system cannot,

Oh but it can.  You underestimate the capabilities of a linear bounded
automaton.

In the case of an LBA and a one-counter machine, essentially your setup,
I claim that when the one-counter machine does nothing but keep
incrementing its counter and at the n-th step put a marker on the tape n
places from the end of the input to delimit the end of the tape, this
combination is already sufficient for universality.

Let S be the common tape alphabet of all the following machines, and let
d be a symbol in S.  Let T be any Turing machine.  Construct T' which
simulates T but which diverges (permanently enters a non-halting state)
the first time the head arrives at a cell containing d.  Construct T''
from T' by prefixing the program of T' with a short routine that first
goes to the end of the tape, writes d one cell beyond the end to serve
as a delimiter, returns to the beginning of the tape, and proceeds to
simulate T'.

Now T' accepts the same set of words on S\{d} (S less symbol d) as T,
whence if T never writes d, then if T is universal on S\{d} so is T'.
T'' on the other hand uses no more tape than the length of the input,
and is therefore a linear bounded automaton.

The system you run for finitely many steps corresponds to T' in this
argument---you have a machine that an encoder can communicate an initial
condition to and it then runs for n steps.  The team formed by T' and
the encoder at each stage then amounts to T'' each time except that at
each stage T'' is given a different input, one cell longer than before
(in my abstraction of your setup where the encoder keeps moving the end
out one more cell at a time).  Although T'' itself is only an LBA,
repeatedly running it on these increasingly longer inputs allows it to
simulate any computation of T' (and hence T) that does not need more
than that many tape cells.  If T eventually halts, so will T'' on a
sufficiently long input.

Now this all seems to support your argument, since in order to create
T'' having the property that it is universal we had to start with the
assumption that T and hence T' is universal.

However we only started with a universal T in order to prove that there
could exist a T'' with the property that for each input w accepted by T
(and hence by T') there exists a sufficiently large initial condition
allowing T'' to accept w, and conversely that if T (and hence T') does
not accept w then no initial condition suffices.

The problem in your proof is your assumption that if a machine T'' has
universal behaviour in this sense it must have arisen originally as a
universal T.

But what if the 2,3 machine we're trying to prove universal implements
not a universal T but actually T'' itself?   Your setup allows T'' to
behave universally as we saw above, even though T'' is not universal,
because you keep changing the input for T'' until it is long enough to
allow it to perform a universal computation performed by T (or T').

If the 2,3 machine is universal in your sense because its behaviour is
that of T'', then it is an LBA.  I claim that your proof does not rule
out this possibility.

One might argue that the construction of T'' is artificial whereas this
2,3 machine arose "in nature" and nature would not dream of limiting its
universal machines in such an obviously counterproductive way, or that
nature would be very unlikely to do so, or that the manner of selection
of this machine out of three million others must have eliminated that
possibility.  But such arguments are wishful thinking because this 2,3
machine is a Turing machine of unknown capacity and we can exhibit
Turing machines with the behaviour of T'' having limited capacity.  You
have to show that this 2,3 machine is not such a T'' machine.

> There seems to be a lemma in question, which is that if a sequence of
>  systems, each of which reads input and produces output, are set up
> so that each one reads the output of the previous one, and none of
> them are universal, then the resulting system cannot be universal. In
> the case of the prize problem, this lemma was basically incorporated
> into the definition of universality.

This is not how I read the technical details of the problem, which seem
quite unambiguous: "For the purposes of this prize, the treatment of
universality in any particular submission must be considered acceptable
by the Prize Committee."  In other words you're entitled to any
definition of universality that satisfies you as long as it also
satisfies the committee.

I would regard any definition of universality that can classify an LBA
as universal as being too generous.  However this is not for me to
determine but the committee.

I would however expect that if this 2,3 machine really is universal then
it should be possible to exhibit that universality without having to run
it on an increasing set of initial conditions, which without some sort
of further modification can as I show above turn a non-universal machine
into a universal one.

Best regards,
Vaughan Pratt