Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: wij <wyniijj5@gmail.com>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Mon, 19 May 2025 07:54:17 +0800
Organization: A noiseless patient Spider
Lines: 377
Message-ID: <fef6ed5334bb98cd162c9a339ba227f529437e8c.camel@gmail.com>
References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com>
	 <479eebef3bd93e82c8fe363908b254b11d15a799.camel@gmail.com>
	 <1002jkk$2k00a$3@dont-email.me>
	 <05e306f20fcb7c88c497e353aaecd36b30fc752a.camel@gmail.com>
	 <10053hb$3759k$1@dont-email.me>
	 <879b3c552bad9da9885e41a298b570c92bef1aaf.camel@gmail.com>
	 <10061h6$3de5f$1@dont-email.me>
	 <4bce5af2b2b8cd198af611e5d8d56598cab15b0a.camel@gmail.com>
	 <10067ok$3ib39$1@dont-email.me>
	 <e63d3083ddf6b9ab172cc24c07155410d81ce5b4.camel@gmail.com>
	 <1007lrp$3r388$1@dont-email.me>
	 <0cbe88d46c63af596e4d2ad6a846e61b7efb14bb.camel@gmail.com>
	 <1008fhf$53u$1@dont-email.me>
	 <cd31647abcc33f0978415df34ec2c8d41d886591.camel@gmail.com>
	 <100a7e4$efgi$1@dont-email.me>
	 <f94f006b40c3ca204d41be9b4507280a3a4fc17b.camel@gmail.com>
	 <100aolc$hq2u$1@dont-email.me>
	 <943f3512f1c253f770eb41519145d4159c0cd6aa.camel@gmail.com>
	 <100dhiv$167g2$1@dont-email.me>
	 <53caddf143d1319d6aef95fb8b349f6b6e07d288.camel@gmail.com>
	 <100dlrb$16vdn$3@dont-email.me>
	 <bbd53c889659463afb5e655a34eafcaf6482b94f@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Mon, 19 May 2025 01:54:18 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="745d7f42001f5c9522e6574626815520";
	logging-data="1316999"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18sahzo3LdJYTwDiaunnGIY"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:RMkt111Ad+2Z/XUf7Ri9J3e6bG0=
In-Reply-To: <bbd53c889659463afb5e655a34eafcaf6482b94f@i2pn2.org>
Bytes: 18007

On Sun, 2025-05-18 at 19:09 -0400, Richard Damon wrote:
> On 5/18/25 6:09 PM, olcott wrote:
> > On 5/18/2025 4:46 PM, wij wrote:
> > > On Sun, 2025-05-18 at 15:57 -0500, olcott wrote:
> > > > On 5/18/2025 3:35 PM, wij wrote:
> > > > > On Sat, 2025-05-17 at 14:39 -0500, olcott wrote:
> > > > > > On 5/17/2025 2:26 PM, wij wrote:
> > > > > > > On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote:
> > > > > > > > On 17/05/2025 04:01, wij wrote:
> > > > > > > > > On Fri, 2025-05-16 at 23:51 +0100, Mike Terry wrote:
> > > > > > > > > > On 16/05/2025 20:35, wij wrote:
> > > > > > > > > > > On Fri, 2025-05-16 at 16:33 +0100, Mike Terry wrote:
> > > > > > > > > > > > On 16/05/2025 12:40, wij wrote:
> > > > > > > > > > > > > On Fri, 2025-05-16 at 03:26 +0100, Mike Terry wro=
te:
> > > > > > > > > > > > > > On 16/05/2025 02:47, wij wrote:
> > > > > > > > > > > > > > > On Fri, 2025-05-16 at 01:40 +0100, Mike Terry=
 wrote:
> > > > > > > > > > > > > > > > On 15/05/2025 19:49, wij wrote:
> > > > > > > > > > > > > > > > > On Thu, 2025-05-15 at 17:08 +0100, Mike T=
erry wrote:
> > > > > > > > > > > > > > > > > > On 14/05/2025 18:53, wij wrote:
> > > > > > > > > > > > > > > > > > > On Wed, 2025-05-14 at 12:24 -0500, ol=
cott wrote:
> > > > > > > > > > > > > > > > > > > > On 5/14/2025 11:43 AM, wij wrote:
> > > > > > > > > > > > > > > > > > > > > On Wed, 2025-05-14 at 09:51 -0500=
, olcott wrote:
> > > > > > > > > > > > > > > > > > > > > > On 5/14/2025 12:13 AM, wij wrot=
e:
> > > > > > > > > > > > > > > > > > > > > > > Q: Write a turing machine tha=
t performs D function=20
> > > > > > > > > > > > > > > > > > > > > > > (which
> > > > > > > > > > > > > > > > > > > > > > > calls
> > > > > > > > > > > > > > > > > > > > > > > itself):
> > > > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > > > void D() {
> > > > > > > > > > > > > > > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 D();
> > > > > > > > > > > > > > > > > > > > > > > }
> > > > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > > > Easy?
> > > > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > > That is not a TM.
> > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > It is a C program that exists. Th=
erefore, there must=20
> > > > > > > > > > > > > > > > > > > > > be a
> > > > > > > > > > > > > > > > > > > > > equivalent
> > > > > > > > > > > > > > > > > > > > > TM.
> > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > > To make a TM that references it=
self the closest
> > > > > > > > > > > > > > > > > > > > > > thing is a UTM that simulates i=
ts own TM source-code.
> > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > > How does a UTM simulate its own T=
M source-code?
> > > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > > You run a UTM that has its own sour=
ce-code on its tape.
> > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > > What is exactly the source-code on it=
s tape?
> > > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > Every UTM has some scheme which can be =
applied to a (TM=20
> > > > > > > > > > > > > > > > > > & input tape)
> > > > > > > > > > > > > > > > > > that
> > > > > > > > > > > > > > > > > > is to
> > > > > > > > > > > > > > > > > > be
> > > > > > > > > > > > > > > > > > simulated.
> > > > > > > > > > > > > > > > > > The
> > > > > > > > > > > > > > > > > > scheme says how to turn the (TM + input=
 tape) into a=20
> > > > > > > > > > > > > > > > > > string of symbols
> > > > > > > > > > > > > > > > > > that
> > > > > > > > > > > > > > > > > > represent
> > > > > > > > > > > > > > > > > > that
> > > > > > > > > > > > > > > > > > computation.
> > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > So to answer your question, the "source=
-code on its=20
> > > > > > > > > > > > > > > > > > tape" is the result
> > > > > > > > > > > > > > > > > > of
> > > > > > > > > > > > > > > > > > applying
> > > > > > > > > > > > > > > > > > the
> > > > > > > > > > > > > > > > > > UTM's
> > > > > > > > > > > > > > > > > > particular scheme to the combination (U=
TM, input tape)=20
> > > > > > > > > > > > > > > > > > that is to be
> > > > > > > > > > > > > > > > > > simulated.
> > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > If you're looking for the exact string =
symbols,=20
> > > > > > > > > > > > > > > > > > obviously you would need
> > > > > > > > > > > > > > > > > > to
> > > > > > > > > > > > > > > > > > specify
> > > > > > > > > > > > > > > > > > the
> > > > > > > > > > > > > > > > > > exact
> > > > > > > > > > > > > > > > > > UTM
> > > > > > > > > > > > > > > > > > being used, because every UTM will have=
 a different=20
> > > > > > > > > > > > > > > > > > answer to your
> > > > > > > > > > > > > > > > > > question.
> > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > > Mike.
> > > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > > People used to say UTM can simulate all T=
M. I was=20
> > > > > > > > > > > > > > > > > questing such a UTM.
> > > > > > > > > > > > > > > > > Because you said "Every UTM ...", so what=
 is the source=20
> > > > > > > > > > > > > > > > > of such UTM?
> > > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > > Yes, a UTM can simulate any TM including it=
self.=C2=A0=20
> > > > > > > > > > > > > > > > (Nothing magical changes
> > > > > > > > > > > > > > > > when
> > > > > > > > > > > > > > > > a
> > > > > > > > > > > > > > > > UTM
> > > > > > > > > > > > > > > > simulates
> > > > > > > > > > > > > > > > itself, as opposed to some other TM.)
> > > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > > Supposed UTM exists, and denoted as U(X), X d=
enotes the=20
> > > > > > > > > > > > > > > tape contents of the
> > > > > > > > > > > > > > > encoding of a TM. And, U(X) should function t=
he same like X.
> > > > > > > > > > > > > > > Given instance U(U(f)), it should function li=
ke f from the=20
> > > > > > > > > > > > > > > above definition.
> > > > > > > > > > > > > > > But, U(U(f)) would fall into a 'self-referenc=
e' trap.
> > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > There is no self-reference trap.
> > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > In your notation:
> > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > -=C2=A0 f represents some computation.
> > > > > > > > > > > > > > -=C2=A0 U(f) represents U being run with f on i=
ts tape.
> > > > > > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 Note this is itself a computation, distinct from=20
> > > > > > > > > > > > > > f of course
> > > > > > > > > > > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0 but having the same behaviour.
> > > > > > > > > > > > > > -=C2=A0 U(U(f)) represents U simulating the pre=
vious computation.
> > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > There is no reason U(f) cannot be simulated by =
U.=C2=A0 U will=20
> > > > > > > > > > > > > > have no knowledge that
> > > > > > > > > > > > > > it
> > > > > > > > > > > > > > is
========== REMAINDER OF ARTICLE TRUNCATED ==========