Deutsch English Français Italiano |
<100dlrb$16vdn$3@dont-email.me> View for Bookmarking (what is this?) Look up another Usenet article |
Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: olcott <polcott333@gmail.com> Newsgroups: comp.theory Subject: Re: How to write a self-referencial TM? Date: Sun, 18 May 2025 17:09:47 -0500 Organization: A noiseless patient Spider Lines: 228 Message-ID: <100dlrb$16vdn$3@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> <e63d3083ddf6b9ab172cc24c07155410d81ce5b4.camel@gmail.com> <1007lrp$3r388$1@dont-email.me> <0cbe88d46c63af596e4d2ad6a846e61b7efb14bb.camel@gmail.com> <1008fhf$53u$1@dont-email.me> <cd31647abcc33f0978415df34ec2c8d41d886591.camel@gmail.com> <100a7e4$efgi$1@dont-email.me> <f94f006b40c3ca204d41be9b4507280a3a4fc17b.camel@gmail.com> <100aolc$hq2u$1@dont-email.me> <943f3512f1c253f770eb41519145d4159c0cd6aa.camel@gmail.com> <100dhiv$167g2$1@dont-email.me> <53caddf143d1319d6aef95fb8b349f6b6e07d288.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Mon, 19 May 2025 00:09:48 +0200 (CEST) Injection-Info: dont-email.me; posting-host="54427c6633a8689b841d1d48a1b07f55"; logging-data="1277367"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX196/n9QTtBd770i3FPzBdWm" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:Vd0cmCbR/bRj9+PDix/gqTr8jmw= X-Antivirus-Status: Clean In-Reply-To: <53caddf143d1319d6aef95fb8b349f6b6e07d288.camel@gmail.com> Content-Language: en-US X-Antivirus: Norton (VPS 250518-4, 5/18/2025), Outbound message Bytes: 11286 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 >>>>>>>>>> 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 ========== REMAINDER OF ARTICLE TRUNCATED ==========