--- Vladimir Nesov <[EMAIL PROTECTED]> wrote: > On Sun, May 11, 2008 at 8:57 PM, Matt Mahoney <[EMAIL PROTECTED]> > wrote: > > > > If a machine P could simulate two other machines Q and R (each with n > bits > > of memory), then P needs n+1 bits, n to reproduce all the states of Q > or > > R, and 1 to remember which machine it is simulating. You described a > > machine P that can simulate only P. > > > > You are being obscure again. A machine that I described can simulate > any machine of limited size and number of states. Basically, it is a > universal machine that can run any other machine, one of which is P, > "the machine itself", but other machines are allowed too. Each machine > can initiate loading of another machine on the underlying universal > machine.
You have only shown that P can simulate itself with no additional memory. If it simulates any other machine, then you need to show that no additional memory is needed for those machines too. Also, it doesn't make sense to talk about "universal" finite state machines, because there are only a finite number of unique programs it can simulate. Instead we can define a machine as general purpose if it can accept 2 or more program specifications (which can be as small as 1 bit). So let me restate my claim. We say that P simulates Q if for all x, P((Q,x)) = Q(x). We say P is general purpose if there exists Q and R such that P simulates both, and there is an x such that Q(x) != R(x) (i.e. Q and R are different programs). Then I claim there is no general purpose finite state machine P that can simulate itself. -- Matt Mahoney, [EMAIL PROTECTED] ------------------------------------------- agi Archives: http://www.listbox.com/member/archive/303/=now RSS Feed: http://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: http://www.listbox.com/member/?member_id=8660244&id_secret=101455710-f059c4 Powered by Listbox: http://www.listbox.com
