Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Mikko Newsgroups: comp.theory Subject: Re: How to write a self-referencial TM? Date: Sun, 18 May 2025 11:20:27 +0300 Organization: - Lines: 211 Message-ID: <100c58b$tdeq$1@dont-email.me> 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> <100aolc$hq2u$1@dont-email.me> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Sun, 18 May 2025 10:20:28 +0200 (CEST) Injection-Info: dont-email.me; posting-host="a208489f75bceb31eee11e8dc89e7bab"; logging-data="964058"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19idoUTd3zhjKgtFYyUQNH8" User-Agent: Unison/2.2 Cancel-Lock: sha1:DgsBaqRiA/rYAplbv8vF488kGTs= On 2025-05-17 19:39:24 +0000, olcott said: > 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 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. >>>>>> >>>>>> TM has no I/O mechanism. 'Computation' always means the contents of the tape >>>>>> is defined (fixed before run). >>>>>> >>>>> >>>>> Correct, and correct. >>>>> >>>>> So... What do you mean "the contents of the tape would not be defined"? >>>>> >>>>> >>>>> Mike. >>>> >>>> In "UTM simulates itself", denoted as U(U(f)), the f would not be defined. >>> >>> Eh?  The f was something /you/ introduced!  You said it represents some >>> computation which UTM U >>> simulates.  How can f suddenly become undefined after you defined it? >>> >>> Do you mean that f would not be on the input tape for (outer)U?  That's >>> not the case at all.  In >>> U(f), the input tape for U contains a representation of f.  When >>> (outer)U simulates (inner)U >>> simulating f, (outer)U's tape contains a representation of computation >>> U(f), which internally >>> contains the original representation of f.  The f is still there and >>> equally well defined in >>> U(U(f)). >>> >>> I think you would benefit from being more explicit and generally more >>> careful in your notation! >>> >>> Using notation to mean U's input tape representation of "TM P, >>> running with input I": >>> ========== REMAINDER OF ARTICLE TRUNCATED ==========