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: Fri, 16 May 2025 09:47:50 +0800
Organization: A noiseless patient Spider
Lines: 139
Message-ID: <4bce5af2b2b8cd198af611e5d8d56598cab15b0a.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>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Fri, 16 May 2025 03:47:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="746533a96eeb3cf7efee6378a768121a";
	logging-data="3594709"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19P+d4rRi6O9LLpWFwe6fbt"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:7CpvKTBZcnaJ4kebmNJvXzwz7KA=
In-Reply-To: <10061h6$3de5f$1@dont-email.me>
Bytes: 6997

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 function (which c=
alls itself):
> > > > > > > >=20
> > > > > > > > void D() {
> > > > > > > > =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 must be a equiv=
alent TM.
> > > > > >=20
> > > > > > > To make a TM that references itself the closest
> > > > > > > thing is a UTM that simulates its own TM source-code.
> > > > > >=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 tape.
> > > >=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.=C2=A0
> > > The
> > > scheme says how to turn the (TM + input tape) into a string of symbol=
s that represent that
> > > computation.
> > >=20
> > > So to answer your question, the "source-code on its tape" is the resu=
lt of applying the UTM's
> > > particular scheme to the combination (UTM, input tape) that is to be =
simulated.
> > >=20
> > > If you're looking for the exact string symbols, obviously you would n=
eed to specify the exact
> > > UTM
> > > being used, because every UTM will have a different answer to your qu=
estion.
> > >=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 (Nothing magical c=
hanges when a UTM simulates=20
> itself, as opposed to some other TM.)

Supposed UTM exists, and denoted as U(X), X denotes the tape contents of th=
e
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 above definition=
..
But, U(U(f)) would fall into a 'self-reference' trap.

> Your question "what is the source of such UTM?" seems to be asking to be =
pointed to some sample=20
> source code for a UTM?=C2=A0 I don't have any!=C2=A0 But I'm sure someone=
 somewhere will have gone to all the=20
> trouble of coding an actual UTM, and will have made that available online=
 somewhere.=C2=A0 Note that a=20
> UTM is a firstly a TM, but TMs can be described as text "source code" and=
 someone could have made=20
> that available online.
>=20
> Perhaps someone else here knows of useful sources for this?=C2=A0 Otherwi=
se you would need to search for=20
> it with Google or whatever.=C2=A0=C2=A0 IF THIS IS WHAT YOU REALLY WANT, =
which seems unlikely to me.
>=20
> Most people aren't interested in specific source code for an actual UTM, =
because the role of a UTM=20
> is /theoretical/, and most people can /see/ what a UTM needs to do, and h=
ow it can do it, so there=20
> is no doubt in their mind that such a UTM /could/ be written.=C2=A0 I dar=
esay that most programmers could
> easily write one themselves, were it not for the huge burden of having to=
 work within the TM=20
> architecture with only the low level facilities TMs provide.=C2=A0 So the=
y consider it a lot of work, and
> at the end they would have a UTM source code, but /what would they plan t=
o do with it/ ??=C2=A0 You would
> only do all this work if you needed to actually /use/ the UTM, but TMs ar=
e not /intended/ as a=20
> practical programming tool.
>=20
> So... Do you /really/ need an actual UTM source code? I wonder.=C2=A0 Wha=
t do you intend to use it for?
>=20
> If you need to develop/test/debug your own TMs, rather than a UTM source =
code you need some kind of=20
> TM development environment.=C2=A0 I don't know if such a thing exists for=
 serious use!
>=20
> If you're just playing/learning about TMs then probably you really just w=
ant a very basic TM=20
> emulator (NOT a UTM) that can take a TM description and output for you th=
e successive steps of its=20
> execution, showing the tape contents and position of the tape head.=C2=A0=
 Loads of (most?) CS students=20
> will have done this themselves at some point, using their own favourite l=
anguage - you could use=20
> Python, C++, Java, whatever you like.=C2=A0 I once wrote myself one of th=
ese as a play thing in C++ and=20
> it took a few hours perhaps.=C2=A0 (Most of the time was fiddling with ou=
tput formats to make the output=20
> appear in a way I liked.=C2=A0 I got bored eventually!)=C2=A0 You could d=
o this yourself...
>=20
> Or... is it that you don't /understand/ something about UTMs and need con=
vincing?=C2=A0 I think just=20
> explaining what is confusing you and asking questions would be a better w=
ay to go!
>=20
> Mike.

No need to make things such complicated and thus unnecessary long comments.=
=C2=A0
We can simply assume the 'source-code' is machine code, the debuger in ever=
y OS is already a 'UTM'
except it cannot simulate itself....  No UTM exists that can simulate any T=
M including itself.=20