Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory Subject: Re: How to write a self-referencial TM? Date: Sat, 17 May 2025 16:07:14 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <400cb81f2e29be1af36661ffee339c996cf97f34@i2pn2.org> 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> <1007lrp$3r388$1@dont-email.me> <0cbe88d46c63af596e4d2ad6a846e61b7efb14bb.camel@gmail.com> <1008fhf$53u$1@dont-email.me> <100a7e4$efgi$1@dont-email.me> <100ap2g$i1dj$1@dont-email.me> <100apj2$i209$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sat, 17 May 2025 20:07:14 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="788723"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird Content-Language: en-US X-Spam-Checker-Version: SpamAssassin 4.0.0 In-Reply-To: <100apj2$i209$1@dont-email.me> On 5/17/25 3:55 PM, olcott wrote: > On 5/17/2025 2:46 PM, Mike Terry wrote: >> On 17/05/2025 20:26, wij wrote: >>> On Sat, 2025-05-17 at 15:45 +0100, Mike Terry wrote: >>>> On 17/05/2025 04:01, wij wrote: >>>>> 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 function >>>>>>>>>>>>>>>>>>> (which calls >>>>>>>>>>>>>>>>>>> itself): >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> void D() { >>>>>>>>>>>>>>>>>>>           D(); >>>>>>>>>>>>>>>>>>> } >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> Easy? >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> That is not a TM. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> It is a C program that exists. Therefore, there must be >>>>>>>>>>>>>>>>> a equivalent TM. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>>> To make a TM that references itself the closest >>>>>>>>>>>>>>>>>> thing is a UTM that simulates its own TM source-code. >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>>> How does a UTM simulate its own TM source-code? >>>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> >>>>>>>>>>>>>>>> You run a UTM that has its own source-code on its tape. >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> What is exactly the source-code on its tape? >>>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> 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 >>>>>>>>>>>>>> string of symbols that >>>>>>>>>>>>>> represent >>>>>>>>>>>>>> that >>>>>>>>>>>>>> computation. >>>>>>>>>>>>>> >>>>>>>>>>>>>> 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. >>>>>>>>>>>>>> >>>>>>>>>>>>>> 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 answer >>>>>>>>>>>>>> to your question. >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> Mike. >>>>>>>>>>>>> >>>>>>>>>>>>> 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? >>>>>>>>>>>> >>>>>>>>>>>> Yes, a UTM can simulate any TM including itself.  (Nothing >>>>>>>>>>>> magical changes when a >>>>>>>>>>>> UTM >>>>>>>>>>>> simulates >>>>>>>>>>>> itself, as opposed to some other TM.) >>>>>>>>>>> >>>>>>>>>>> Supposed UTM exists, and denoted as U(X), X denotes the tape >>>>>>>>>>> contents 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 >>>>>>>>>>> above definition. >>>>>>>>>>> But, U(U(f)) would fall into a 'self-reference' trap. >>>>>>>>>> >>>>>>>>>> There is no self-reference trap. >>>>>>>>>> >>>>>>>>>> In your notation: >>>>>>>>>> >>>>>>>>>> -  f represents some computation. >>>>>>>>>> -  U(f) represents U being run with f on its tape. >>>>>>>>>>         Note this is itself a computation, distinct from f of >>>>>>>>>> course >>>>>>>>>>         but having the same behaviour. >>>>>>>>>> -  U(U(f)) represents U simulating the previous computation. >>>>>>>>>> >>>>>>>>>> There is no reason U(f) cannot be simulated by U.  U will have >>>>>>>>>> no knowledge that it is >>>>>>>>>> "simulating >>>>>>>>>> itself", and will just simulate what it is given. >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> 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 tape >>>>>>>>> would not be defined. Saying "UTM can simulate any TM" is >>>>>>>>> misleading because >>>>>>>>> no such TM (UTM as TM) exists. >>>>>>>> >>>>>>>> What do you mean "the contents of the tape would not be >>>>>>>> defined"?  A TM is /equipped/ with >>>>>>>> an >>>>>>>> infinite tape, but the /contents/ of that tape are not a part of >>>>>>>> that TM's definition. >>>>>>>> >>>>>>>> For example we could build a TM P that decides whether a number >>>>>>>> is prime.  Given a number n, >>>>>>>> we >>>>>>>> convert n into the input tape representation of n, and run P >>>>>>>> with that tape as input. >>>>>>>> >>>>>>>> It's essentially no different for UTMs.  Such a UTM certainly is >>>>>>>> a "complete TM", equipped >>>>>>>> with >>>>>>>> its >>>>>>>> own input tape.  Of course we don't know what's on the input >>>>>>>> tape because nobody has said >>>>>>>> yet >>>>>>>> what >>>>>>>> computation we are asking it to simulate!  [Similarly we don't >>>>>>>> know what's on P's input >>>>>>>> tape, >>>>>>>> until >>>>>>>> we know what n we want it to test for primeness.]  Once you say >>>>>>>> what computation you want >>>>>>>> the >>>>>>>> UTM to >>>>>>>> simulate we can build a tape string to perform that particular >>>>>>>> simulation.  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. >>>>>>>> >>>>>>>> >>>>>>>> Mike. >>>>>>> ========== REMAINDER OF ARTICLE TRUNCATED ==========