Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!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: Sun, 27 Oct 2024 17:05:52 +0800
Organization: A noiseless patient Spider
Lines: 89
Message-ID: <3e5615675e693ccde63cb74baed09251a2b83467.camel@gmail.com>
References: <8378f81fb465a4d56d7c65b466790571c71a5c31.camel@gmail.com>
	 <a737237de974cafe1366079cc5923b6f7cac6029@i2pn2.org>
	 <bedc2992ff0433fe5abfe8e572a75b1a44a67884.camel@gmail.com>
	 <vfj28h$3j3qf$4@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Sun, 27 Oct 2024 10:05:53 +0100 (CET)
Injection-Info: dont-email.me; posting-host="cb573552714cb9d77c9de13a369341c7";
	logging-data="277837"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+EdmEdwNxD9as3/dJ7q8GS"
User-Agent: Evolution 3.50.2 (3.50.2-1.fc39)
Cancel-Lock: sha1:NeSHn3I1cEDOrgGZiffXDOXmw7Y=
In-Reply-To: <vfj28h$3j3qf$4@i2pn2.org>
Bytes: 4751

On Sat, 2024-10-26 at 11:35 -0400, Richard Damon wrote:
> On 10/26/24 10:08 AM, wij wrote:
> > 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, eve=
ry one 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
> > > 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 j=
ust
> > > ends up being a non-halting computation, and thus the non-halting
> > > emulation of that computation is exactly right.
> > >=20
> > > The problem is if you want it to be a UTM and also a decider, then yo=
u
> > > run into the problem.
> > >=20
> > > The UTM chain *IS* an infinite deep recursive simulation, which is ju=
st
> > > 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
> > > finds it can't know the answer for the behavior of the UTM it was
> > > previously.
> >=20
> > Simulator::=3D A TM (utm) that performs the same function as its argume=
nt TM (f).
> > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 IOW, utm(f)=3Df=C2=A0 (or utm(f,arg)=3Df(arg))
> >=20
> > 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'?
> >=20
> > How do you define 'simulator'? What exactly does UTM simulate?
> >=20
> >=20
>=20
> So, what does utm() do, one good definition is just halt.
>=20
> thus utm(utm) would emulate utm() which would just see it doesn't have=
=20
> an input and halt.
>=20
> UTMs are given a "description" of the Turing Machne and of its input,=20
> expressed in the "language" of the UTM.
>=20
> A simple (to understand,complicated to build) would be one where you=20
> give as an input listing of every possible state the machine could be in=
=20
> and every possible input character, and lists the resulting state,=20
> character to put on the tape, and tape motion, and the starting state,=
=20
> Then you put the contents of the tape that machine is to process with=20
> the current pointer of the starting point.
>=20
> The UTM then just applies the rules described in the first part, to the=
=20
> tape described in the second part, and when it gets to a state marked as=
=20
> a final state (perhaps one of the tape operations is "Halt", or states=
=20
> are marked as terminal) it stops and returns the results.
>=20
> This means that the UTM just "zimulates" the execution process of a=20
> Turing Machine, where one "step" takes the current state, and the=20
> contents of the tape at its current position, and updates the tape to=20
> the new value and move the current location of the tape, and updates the=
=20
> current state.
>=20
> The "proof" of the existance of a UTM was the proof that a Turing=20
> Machine could be programmed to do that set of transformations.
>=20

That's right. You need to REPROGRAM. You need to modify the transition func=
tion and
the symbols, and the tape contents.=C2=A0
Therefore, "No real UTM exists". "An Univeral TM" is a false idea.