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: Thu, 15 May 2025 15:50:34 -0500 Organization: A noiseless patient Spider Lines: 120 Message-ID: <1005k2r$3akrk$2@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> <0e800ac26a88cee27ea427998d53c9e5427b530c.camel@gmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Thu, 15 May 2025 22:50:35 +0200 (CEST) Injection-Info: dont-email.me; posting-host="66a8f7019eb14522c3a913b396c0eecb"; logging-data="3494772"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX183cgfdNqFDy4ECJ2eStYi5" User-Agent: Mozilla Thunderbird Cancel-Lock: sha1:0rookTGXJVTxyzm1ZqU2a0j9XgI= X-Antivirus: Norton (VPS 250515-4, 5/15/2025), Outbound message X-Antivirus-Status: Clean In-Reply-To: <0e800ac26a88cee27ea427998d53c9e5427b530c.camel@gmail.com> Content-Language: en-US On 5/15/2025 2:57 PM, wij wrote: > On Thu, 2025-05-15 at 11:47 -0500, olcott wrote: >> 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. > > Sort of. > >> If there was such a UTM then examining things >> like a termination analyzer would be too difficult >> because of the volume of details. Even moving a >> single value to a specific memory location can >> take many many steps. > > So, which part of POOH is "fully encoded UTM" > >> A RASP machine >> https://en.wikipedia.org/wiki/Random-access_stored-program_machine >> is a much better fit for examining the details of any >> complex algorithm. >> >> The x86 language is essentially the same thing as a RASP >> machine for all computations that can be accomplished >> with the amount of memory that is available. > > Absolutely false. POOH is the example that rejected TM/RASP instead of C. > > In trying making P!=NP proof (may have defects, I just leave it there to improve) > https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download > I feel TM would be very long and tedious, so I claimed that no *algorithm* can > solve NPC (algorithmic) problems. (thanks to olcott, this proof was inspired in > refuting POOH.) > > See also Spu in my recent post. TM is very low-level to solve many idea of problems. > >> To be a computable function within a model of computation >> a sequence of the steps of a specific algorithm must be >> applied to (an often finite string) input to derive an output. >> https://en.wikipedia.org/wiki/Computable_function >> >> When computing the sum() function the steps of the algorithm >> of arithmetic must be applied to the inputs. >> >> *When computing the halt() function steps with a simulating* >> *termination analyzer the behavioral steps specified by the* >> *input must be simulated according to the computer language* >> *of this input* >> >> *I may be wrong yet it seems to me that* >> Computer science never knew these things before in that >> it never placed any limit on the type of algorithm that >> must be performed. >> >> I think that it was Ben that said that one of two >> functions that do nothing besides return true or false >> is correct on all of the counter-example inputs >> to the halting problem. >> >> When we require that a mapping be computed from an >> input, then this idea is rejected. >> > > You are excellent in quoting tautology to support your claims. > Most people don't know that a mapping must be computed from the inputs, hence Ben's mistake. -- Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius hits a target no one else can see." Arthur Schopenhauer