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: Fri, 16 May 2025 03:57:26 +0800
Organization: A noiseless patient Spider
Lines: 124
Message-ID: <0e800ac26a88cee27ea427998d53c9e5427b530c.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> <10055rn$37m1t$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Injection-Date: Thu, 15 May 2025 21:57:28 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="b7c2e7cb48bac1670f833664c84ad09e";
	logging-data="3442297"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18TMfIToK0uPF4XNzK1AqeK"
User-Agent: Evolution 3.54.3 (3.54.3-1.fc41)
Cancel-Lock: sha1:gdx6n7gWsXHq9O5/BSJZetrh3jY=
In-Reply-To: <10055rn$37m1t$1@dont-email.me>

On Thu, 2025-05-15 at 11:47 -0500, olcott wrote:
> On 5/15/2025 11:08 AM, 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 cal=
ls=20
> > > > > > > itself):
> > > > > > >=20
> > > > > > > void D() {
> > > > > > > =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 equival=
ent=20
> > > > > 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)=
=20
> > that is to be simulated.=C2=A0 The scheme says how to turn the (TM + in=
put=20
> > tape) into a string of symbols that represent that computation.
> >=20
> > So to answer your question, the "source-code on its tape" is the result=
=20
> > of applying the UTM's particular scheme to the combination (UTM, input=
=20
> > tape) that is to be simulated.
> >=20
> > If you're looking for the exact string symbols, obviously you would nee=
d=20
> > to specify the exact UTM being used, because every UTM will have a=20
> > different answer to your question.
> >=20
> >=20
> > Mike.
> >=20
>=20
> These things cannot be investigated in great
> depth because there is no fully encoded UTM in
> any standard language.

Sort of.

> If there was such a UTM then examining things
> like a termination analyzer would be too difficult
> because of the volume of details. Even moving a
> single value to a specific memory location can
> take many many steps.

So, which part of POOH is "fully encoded UTM"

> A RASP machine
> https://en.wikipedia.org/wiki/Random-access_stored-program_machine
> is a much better fit for examining the details of any
> complex algorithm.
>=20
> The x86 language is essentially the same thing as a RASP
> machine for all computations that can be accomplished
> with the amount of memory that is available.

Absolutely false. POOH is the example that rejected TM/RASP instead of C.

In trying making P!=3DNP proof (may have defects, I just leave it there to =
improve)
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/dow=
nload
I feel TM would be very long and tedious, so I claimed that no *algorithm* =
can
solve NPC (algorithmic) problems. (thanks to olcott, this proof was inspire=
d in=20
refuting POOH.)

See also Spu in my recent post. TM is very low-level to solve many idea of =
problems.

> To be a computable function within a model of computation
> a sequence of the steps of a specific algorithm must be
> applied to (an often finite string) input to derive an output.
> https://en.wikipedia.org/wiki/Computable_function
>=20
> When computing the sum() function the steps of the algorithm
> of arithmetic must be applied to the inputs.
>=20
> *When computing the halt() function steps with a simulating*
> *termination analyzer the behavioral steps specified by the*
> *input must be simulated according to the computer language*
> *of this input*
>=20
> *I may be wrong yet it seems to me that*
> Computer science never knew these things before in that
> it never placed any limit on the type of algorithm that
> must be performed.
>=20
> I think that it was Ben that said that one of two
> functions that do nothing besides return true or false
> is correct on all of the counter-example inputs
> to the halting problem.
>=20
> When we require that a mapping be computed from an
> input, then this idea is rejected.
>=20

You are excellent in quoting tautology to support your claims.