Path: ...!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: Richard Damon <richard@damon-family.org>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Sat, 17 May 2025 09:02:16 -0400
Organization: i2pn2 (i2pn.org)
Message-ID: <774e0d81795b6ca5615689a2cb60fa1a0d758898@i2pn2.org>
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>
 <1008ur3$66kl$4@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 17 May 2025 13:08:26 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="746261"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg";
User-Agent: Mozilla Thunderbird
In-Reply-To: <1008ur3$66kl$4@dont-email.me>
Content-Language: en-US
X-Spam-Checker-Version: SpamAssassin 4.0.0
Bytes: 8513
Lines: 184

On 5/16/25 11:12 PM, olcott wrote:
> On 5/16/2025 10:01 PM, 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.
>>
>> I was considering also expressing the idea that undecidable is caused 
========== REMAINDER OF ARTICLE TRUNCATED ==========