Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott Newsgroups: comp.theory Subject: Re: How to write a self-referencial TM? Date: Tue, 20 May 2025 23:36:03 -0500 Organization: A noiseless patient Spider Lines: 282 Message-ID: <100jl7j$2m26r$2@dont-email.me> References: <1e4f1a15826e67e7faf7a3c2104d09e9dadc6f06.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> <100aolc$hq2u$1@dont-email.me> <943f3512f1c253f770eb41519145d4159c0cd6aa.camel@gmail.com> <100dhiv$167g2$1@dont-email.me> <53caddf143d1319d6aef95fb8b349f6b6e07d288.camel@gmail.com> <100dlrb$16vdn$3@dont-email.me> <100f297$1j2o5$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Wed, 21 May 2025 06:36:04 +0200 (CEST) Injection-Info: dont-email.me; posting-host="7faeabb3f4a2e362069c5f0f1728441c"; logging-data="2820315"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/pvn6KpczWOuP6cceFW7Xy" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:orvR4mM32J5E9y8RUaPhZJKOCog= X-Antivirus: Norton (VPS 250521-0, 5/20/2025), Outbound message In-Reply-To: <100f297$1j2o5$1@dont-email.me> X-Antivirus-Status: Clean Content-Language: en-US On 5/19/2025 5:48 AM, Mikko wrote: > On 2025-05-18 22:09:47 +0000, olcott said: > >> On 5/18/2025 4:46 PM, wij wrote: >>> On Sun, 2025-05-18 at 15:57 -0500, olcott wrote: >>>> On 5/18/2025 3:35 PM, wij wrote: >>>>> On Sat, 2025-05-17 at 14:39 -0500, olcott wrote: >>>>>> On 5/17/2025 2:26 PM, 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 ========== REMAINDER OF ARTICLE TRUNCATED ==========