[FOM] Smallest universal machine

[Vaughan Pratt]

Hector Zenil wrote:
> On 10/30/07, Vaughan Pratt <pratt at cs.stanford.edu> wrote:
>> Hector Zenil wrote:
>>> One could fairly argue that two non-universal coupled automata can reach
>>  >universality, but it would require the couple to interact at every step,
>>
>> Thank you, this nicely boils the fallacy down from 55 pages to two
>> lines.  Merely providing an initial condition saying how long to run is
>> sufficient to turn a nonuniversal machine such as an LBA into a
>> universal one, without any further interaction.
>>
>> Vaughan Pratt
> 
> 
> That quote is from my reply to your 10/27 post (below), in which you
> were talking about pushdown automata (PDAs) interacting at every step.
> My response correctly noted that was not the case in Alex Smith's
> proof. You later agreed with me on your 10/30 post since you had not
> considered the communication requirement between the two machines
> (performed at the start, one-way and off-line in Smith's
> construction).

I'm afraid I'm having difficulty following the reasoning here.  The post 
of yours that I responded to made no mention of my 10/27 post you quote 
here.  Furthermore that post used two PDAs only to point out a bug in my 
first attempt at a definition of universality, not to point out a bug in 
Smith's proof.  My following message to FOM pointing out a bug in 
Smith's proof raised the objection that the same reasoning Smith uses 
would show that an LBA is universal.  Nothing in that objection involved 
PDAs.

> You are now talking about linear bounded automata (LBA), changing your
> first argument.

As I said, my "first argument" in that 10/27 was an objection to my 
argument, not to Smith's.  I don't understand your message at all.

Vaughan Pratt