--- Vladimir Nesov <[EMAIL PROTECTED]> wrote: > On Sat, May 10, 2008 at 5:01 AM, Matt Mahoney <[EMAIL PROTECTED]> > wrote: > > > > OK, let me make more clear the distinction between running a program > and > > simulating it. Say that a program P simulates a program Q if for all > y, > > P((Q,y)) = "the output is "+Q(y) where + means string concatenation. > In > > other words, given Q and y, P prints not Q(y) but a statement > describing > > what the output Q(y) would be. Then I claim there is no finite state > > machine P that can simulate itself (including the trivial case). P > needs > > as many states as Q to simulate it, plus additional states to print > "the > > output is ". > > > > If you don't limit the length of the input, recognized languages can > only be regular, and so I can't, for example, match pairs of brackets. > But if input has format "simulate this on yourself: "+y, then there is > no problem: I just print a "the output is " in response to "simulate > this on yourself: " and go on as usual, starting to simulate y even if > it too starts with "simulate this on yourself: ". You don't need > "additional" state if it's already there.
Yes, but in this case the input to P is not (P,y), it is a self reference to whatever program P is running plus y. I think you would agree that a virtual machine with n bits of memory can only be implemented on a machine with more than n bits of memory. -- 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
