Path: ...!weretis.net!feeder9.news.weretis.net!i2pn.org!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: No TM exists that can simulate all TM.
Date: Fri, 25 Oct 2024 18:17:32 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <a737237de974cafe1366079cc5923b6f7cac6029@i2pn2.org>
References: <8378f81fb465a4d56d7c65b466790571c71a5c31.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Fri, 25 Oct 2024 22:17:32 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="3665457"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
X-Spam-Checker-Version: SpamAssassin 4.0.0
Content-Language: en-US
In-Reply-To: <8378f81fb465a4d56d7c65b466790571c71a5c31.camel@gmail.com>
Bytes: 1949
Lines: 23

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?
> https://en.wikipedia.org/wiki/Universal_Turing_machine
> 

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.