Deutsch   English   Français   Italiano  
<cd31647abcc33f0978415df34ec2c8d41d886591.camel@gmail.com>

View for Bookmarking (what is this?)
Look up another Usenet article

Path: 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: Sat, 17 May 2025 11:01:45 +0800
Organization: A noiseless patient Spider
Lines: 192
Message-ID: <cd31647abcc33f0978415df34ec2c8d41d886591.camel@gmail.com>
References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.camel@gmail.com>
	 <1002akp$2i4bk$2@dont-email.me>
	 <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>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Sat, 17 May 2025 05:01:46 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3412a21caf2437e4363b303de818a885";
	logging-data="195344"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+qXZtnP1Te3EkE9hluRP9A"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:dzGXgYx7TX0/kJCZBPNPQAkAob0=
In-Reply-To: <1008fhf$53u$1@dont-email.me>

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 wrote:
> > > > > 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 Terry wrote:
> > > > > > > > > On 14/05/2025 18:53, wij wrote:
> > > > > > > > > > On Wed, 2025-05-14 at 12:24 -0500, olcott 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 wrote:
> > > > > > > > > > > > > > Q: Write a turing machine that performs D funct=
ion (which calls itself):
> > > > > > > > > > > > > >=20
> > > > > > > > > > > > > > void D() {
> > > > > > > > > > > > > > =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. Therefore, there mus=
t be a equivalent TM.
> > > > > > > > > > > >=20
> > > > > > > > > > > > > To make a TM that references itself the closest
> > > > > > > > > > > > > thing is a UTM that simulates its own TM source-c=
ode.
> > > > > > > > > > > >=20
> > > > > > > > > > > > How does a UTM simulate its own TM source-code?
> > > > > > > > > > > >=20
> > > > > > > > > > >=20
> > > > > > > > > > > You run a UTM that has its own source-code on its tap=
e.
> > > > > > > > > >=20
> > > > > > > > > > What is exactly the source-code on its tape?
> > > > > > > > > >=20
> > > > > > > > >=20
> > > > > > > > > Every UTM has some scheme which can be applied to a (TM &=
 input tape) that is to be
> > > > > > > > > simulated.
> > > > > > > > > The
> > > > > > > > > scheme says how to turn the (TM + input tape) into a stri=
ng of symbols that
> > > > > > > > > represent
> > > > > > > > > that
> > > > > > > > > computation.
> > > > > > > > >=20
> > > > > > > > > So to answer your question, the "source-code on its tape"=
 is the result of applying
> > > > > > > > > the
> > > > > > > > > UTM's
> > > > > > > > > particular scheme to the combination (UTM, input tape) th=
at is to be simulated.
> > > > > > > > >=20
> > > > > > > > > If you're looking for the exact string symbols, obviously=
 you would need to specify
> > > > > > > > > the
> > > > > > > > > exact
> > > > > > > > > UTM
> > > > > > > > > being used, because every UTM will have a different answe=
r to your question.
> > > > > > > > >=20
> > > > > > > > >=20
> > > > > > > > > Mike.
> > > > > > > >=20
> > > > > > > > People used to say UTM can simulate all TM. I was questing =
such a UTM.
> > > > > > > > Because you said "Every UTM ...", so what is the source of =
such UTM?
> > > > > > >=20
> > > > > > > Yes, a UTM can simulate any TM including itself.=C2=A0 (Nothi=
ng magical changes when a UTM
> > > > > > > simulates
> > > > > > > itself, as opposed to some other TM.)
> > > > > >=20
> > > > > > Supposed UTM exists, and denoted as U(X), X denotes the tape co=
ntents of the
> > > > > > encoding of a TM. And, U(X) should function the same like X.
> > > > > > Given instance U(U(f)), it should function like f from the abov=
e definition.
> > > > > > But, U(U(f)) would fall into a 'self-reference' 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 its tape.
> > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Note this is itself a computation,=
 distinct from f of course
> > > > > =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 but having the same behaviour.
> > > > > -=C2=A0 U(U(f)) represents U simulating the previous computation.
> > > > >=20
> > > > > There is no reason U(f) cannot be simulated by U.=C2=A0 U will ha=
ve no knowledge that it is
> > > > > "simulating
> > > > > itself", and will just simulate what it is given.
> > > > >=20
> > > > >=20
> > > > > Mike.
> > > >=20
> > > > Sorry for not being clear on the UTM issue (I wanted to mean severa=
l things in one post).
> > > > You are right there is no self-reference.
> > > > I mean 'UTM' is not a complete, qualified TM because the contents o=
f the tape
> > > > would not be defined. Saying "UTM can simulate any TM" is misleadin=
g because
> > > > no such TM (UTM as TM) exists.
> > >=20
> > > What do you mean "the contents of the tape would not be defined"?=C2=
=A0 A TM is /equipped/ with an
> > > infinite tape, but the /contents/ of that tape are not a part of that=
 TM's definition.
> > >=20
> > > For example we could build a TM P that decides whether a number is pr=
ime.=C2=A0 Given a number n, we
> > > convert n into the input tape representation of n, and run P with tha=
t tape as input.
> > >=20
> > > It's essentially no different for UTMs.=C2=A0 Such a UTM certainly is=
 a "complete TM", equipped with
> > > its
> > > own input tape.=C2=A0 Of course we don't know what's on the input tap=
e because nobody has said yet
> > > what
> > > computation we are asking it to simulate!=C2=A0 [Similarly we don't k=
now what's on P's input tape,
> > > until
> > > we know what n we want it to test for primeness.]=C2=A0 Once you say =
what computation you want the
> > > UTM to
> > > simulate we can build a tape string to perform that particular simula=
tion.=C2=A0 That is the case
> > > /whatever/ computation we come up with, so it is simply the case [not=
 misleading] that the UTM
> > > can
> > > simulate any computation.
> > >=20
> > >=20
> > > Mike.
> >=20
> > TM has no I/O mechanism. 'Computation' always means the contents of the=
 tape
> > is defined (fixed before run).
> >=20
>=20
> Correct, and correct.
>=20
> So... What do you mean "the contents of the tape would not be defined"?
>=20
>=20
> Mike.

In "UTM simulates itself", denoted as U(U(f)), the f would not be defined.

I was considering also expressing the idea that undecidable is caused by 's=
emantic
self reference'.
Ex1: The truth value of "This sentence is true" is also undecidable.=C2=A0

Ex2: The following D is also a valid HP counter-example:
========== REMAINDER OF ARTICLE TRUNCATED ==========