Path: ...!eternal-september.org!feeder2.eternal-september.org!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: joes <noreply@example.org>
Newsgroups: comp.theory
Subject: Re: No TM exists that can simulate all TM.
Date: Sat, 26 Oct 2024 16:18:34 -0000 (UTC)
Organization: i2pn2 (i2pn.org)
Message-ID: <vfj4oq$3iq0i$4@i2pn2.org>
References: <8378f81fb465a4d56d7c65b466790571c71a5c31.camel@gmail.com>
	<a737237de974cafe1366079cc5923b6f7cac6029@i2pn2.org>
	<bedc2992ff0433fe5abfe8e572a75b1a44a67884.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 26 Oct 2024 16:18:34 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3762194"; mail-complaints-to="usenet@i2pn2.org"
User-Agent: Pan/0.145 (Duplicitous mercenary valetism; d7e168a
 git.gnome.org/pan2)
Bytes: 2617
Lines: 34

Am Sat, 26 Oct 2024 22:08:23 +0800 schrieb wij:
> On Fri, 2024-10-25 at 18:17 -0400, Richard Damon wrote:
>> On 10/25/24 1:12 PM, wij wrote:
>> > Proof: Simulating self is not possible (from all real programs, every
>> > one can verify).
>> > This also implies UTM does not exist.
>> > Did Turing made a mistake?
>> > 
>> The key point you are missing is that if the UTM emulating a program
>> like H^ (without the contrary nature at the end), so that we can get
>> the infinite chain of UTM emulating that UTM emulating that UTM ..., it
>> just ends up being a non-halting computation, and thus the non-halting
>> emulation of that computation is exactly right.
>> The problem is if you want it to be a UTM and also a decider, then you
>> run into the problem.
>> The UTM chain *IS* an infinite deep recursive simulation, which is just
>> like the infinite-recursion, which is non-halting.
>> When you change the UTM to be a decider (and thus no longer a UTM) it
>> finds it can't know the answer for the behavior of the UTM it was
>> previously.
> 
> Simulator::= A TM (utm) that performs the same function as its argument
> TM (f).
>              IOW, utm(f)=f  (or utm(f,arg)=f(arg))
> In case of self-simulation "utm(utm)" ... well, the argument utm has no
> argument (empty tape?) to define its behavior. What is the outer utm
> supposed to 'simulate'?
> How do you define 'simulator'? What exactly does UTM simulate?
You also need an input for the simulated machine. I suppose you would
want an infinite chain of UTMs simulating themselves simulating 
themselves (sic).

-- 
Am Sat, 20 Jul 2024 12:35:31 +0000 schrieb WM in sci.math:
It is not guaranteed that n+1 exists for every n.