On Sun, May 11, 2008 at 9:45 PM, Matt Mahoney <[EMAIL PROTECTED]> wrote: > > 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. >
I have an impression of chasing an invisible dragon ( http://www.overcomingbias.com/2007/07/belief-in-belie.html ). As you didn't describe what a "program" is, there is no distinction between a program and its argument. Your requirement for Q and R with y such that Q(y)!=R(y) is thus equivalent to there being two inputs Qy and Ry with equal suffixes y, such that P(Qy)!=P(Ry). Plus, to implement "self-simulation", there must be a prefix P such that P(Px)="simulating P: "+P(x), for all strings x. Fine, a solution. I'm going to use Mealy machine formalism ( http://en.wikipedia.org/wiki/Mealy_machine ). Let y be an empty string, Q equal to "Q", R to "R" and P to "P". Then, P has a single state with trivial transition function, and with output function that outputs "simulating P: " on input 'P', "I am Q;" on input 'Q', "I am R;" on input 'R', and "I understand perfectly what you mean;" on any other input. As far as I can see, it meets all your current criteria. -- Vladimir Nesov [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
