Path: ...!eternal-september.org!feeder2.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: No TM exists that can simulate all TM.
Date: Sat, 26 Oct 2024 22:08:23 +0800
Organization: A noiseless patient Spider
Lines: 43
Message-ID: <bedc2992ff0433fe5abfe8e572a75b1a44a67884.camel@gmail.com>
References: <8378f81fb465a4d56d7c65b466790571c71a5c31.camel@gmail.com>
	 <a737237de974cafe1366079cc5923b6f7cac6029@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Sat, 26 Oct 2024 16:08:24 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="2e4e165f6431a2457ea5775b9dbd60c2";
	logging-data="3944469"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19XWbvwHmtZ9Pmo2cIK+ucF"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:22fQrp+4li4vY9Yi0A0yKmuQC24=
In-Reply-To: <a737237de974cafe1366079cc5923b6f7cac6029@i2pn2.org>
Bytes: 2614

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 o=
ne can verify).
> >=20
> > This also implies UTM does not exist.
> >=20
> > Did Turing made a mistake?
> > https://en.wikipedia.org/wiki/Universal_Turing_machine
> >=20
>=20
> The key point you are missing is that if the UTM emulating a program=20
> like H^ (without the contrary nature at the end), so that we can get the=
=20
> infinite chain of UTM emulating that UTM emulating that UTM ..., it just=
=20
> ends up being a non-halting computation, and thus the non-halting=20
> emulation of that computation is exactly right.
>=20
> The problem is if you want it to be a UTM and also a decider, then you=
=20
> run into the problem.
>=20
> The UTM chain *IS* an infinite deep recursive simulation, which is just=
=20
> like the infinite-recursion, which is non-halting.
>=20
> When you change the UTM to be a decider (and thus no longer a UTM) it=20
> finds it can't know the answer for the behavior of the UTM it was=20
> previously.

Simulator::=3D A TM (utm) that performs the same function as its argument T=
M (f).
             IOW, utm(f)=3Df  (or utm(f,arg)=3Df(arg))

In case of self-simulation "utm(utm)" ... well, the argument utm has no arg=
ument
(empty tape?) to define its behavior. What is the outer utm supposed to 'si=
mulate'?

How do you define 'simulator'? What exactly does UTM simulate?