Path: 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: 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>
 <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>
 <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 ==========