Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: wij 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.