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 ==========