Deutsch English Français Italiano |
<e63d3083ddf6b9ab172cc24c07155410d81ce5b4.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: Fri, 16 May 2025 19:40:17 +0800 Organization: A noiseless patient Spider Lines: 107 Message-ID: <e63d3083ddf6b9ab172cc24c07155410d81ce5b4.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> MIME-Version: 1.0 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Injection-Date: Fri, 16 May 2025 13:40:19 +0200 (CEST) Injection-Info: dont-email.me; posting-host="746533a96eeb3cf7efee6378a768121a"; logging-data="3929405"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/99gSWIzuYrgkbsjomv9vk" User-Agent: Evolution 3.54.3 (3.54.3-1.fc41) Cancel-Lock: sha1:x4G59oa2PAoJKZrWr1lYk1I0zwg= In-Reply-To: <10067ok$3ib39$1@dont-email.me> 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 function (whi= ch calls itself): > > > > > > > > > >=20 > > > > > > > > > > void D() { > > > > > > > > > > =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 must be a e= quivalent 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 t= ape) that is to be > > > > > simulated. > > > > > The > > > > > scheme says how to turn the (TM + input tape) into a string of sy= mbols 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) that is to= be simulated. > > > > >=20 > > > > > If you're looking for the exact string symbols, obviously you wou= ld need to specify the > > > > > exact > > > > > UTM > > > > > being used, because every UTM will have a different answer to you= r question. > > > > >=20 > > > > >=20 > > > > > Mike. > > > >=20 > > > > People used to say UTM can simulate all TM. I was questing such a U= TM. > > > > 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 magic= al 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 contents o= f 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 above defini= tion. > > 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 Note this is itself a computation, distinct from f of = course > =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 have no kn= owledge that it is "simulating=20 > itself", and will just simulate what it is given. >=20 >=20 > Mike. Sorry for not being clear on the UTM issue (I wanted to mean several things= in one post). You are right there is no self-reference. I mean 'UTM' is not a complete, qualified TM because the contents of the ta= pe would not be defined. Saying "UTM can simulate any TM" is misleading becaus= e no such TM (UTM as TM) exists.