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:41:44 -0500 Organization: A noiseless patient Spider Lines: 86 Message-ID: <100jli8$2m26r$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> <10055rn$37m1t$1@dont-email.me> <1006pc9$3ld84$1@dont-email.me> <1007m9e$3qb7l$17@dont-email.me> <100f1oi$1iukq$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:41:45 +0200 (CEST) Injection-Info: dont-email.me; posting-host="7faeabb3f4a2e362069c5f0f1728441c"; logging-data="2820315"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/YB4YE2fvylKI3KOArEbYE" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:3BmceVw/SuRvQtxHbX5Up+eEj4g= In-Reply-To: <100f1oi$1iukq$1@dont-email.me> X-Antivirus-Status: Clean Content-Language: en-US X-Antivirus: Norton (VPS 250521-0, 5/20/2025), Outbound message On 5/19/2025 5:39 AM, Mikko wrote: > On 2025-05-16 15:40:29 +0000, olcott said: > >> On 5/16/2025 2:27 AM, Mikko wrote: >>> On 2025-05-15 16:47:49 +0000, olcott said: >>> >>>> On 5/15/2025 11:08 AM, 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. >>>> >>>> These things cannot be investigated in great >>>> depth because there is no fully encoded UTM in >>>> any standard language. >>> >>> Investigations do not need a standard language. For an investigation an >>> ad hoc language is good enough and usually better. >> >> Until I made this concrete people kept assuming that >> an input DD could be defined that actually does the >> opposite of whatever value that its simulating termination >> analyzer HHH returns. > > That need not and should not be assumed. That can be constructively > proven. > > Which doesn't matter to any investigation. > There are only two ways to try to define a DD that actually does the opposition of whatever value that is termination analyzer returns. Neither of the work. int main() { DDD() // HHH called from DDD can know nothing of it caller. } -- Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer