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. -- 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
