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: Fri, 16 May 2025 22:58:43 -0500
Organization: A noiseless patient Spider
Lines: 197
Message-ID: <10091hj$6mor$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>
 <1008ur3$66kl$4@dont-email.me>
 <2ac3a719390fc286b455c2cca442bcc3a3955627.camel@gmail.com>
 <10090f3$6mor$1@dont-email.me>
 <727d3a386303190b580af657d72913e899f08218.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 17 May 2025 05:58:44 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="6ea8251727358be87ec7627194d1f4d0";
	logging-data="219931"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+QX6Vx5vcRfPD5nTVvD3Iy"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:0G3e3l1anf+Fh/EZJtya0/nq5BQ=
X-Antivirus: Norton (VPS 250516-6, 5/16/2025), Outbound message
In-Reply-To: <727d3a386303190b580af657d72913e899f08218.camel@gmail.com>
X-Antivirus-Status: Clean
Content-Language: en-US

On 5/16/2025 10:49 PM, wij wrote:
> On Fri, 2025-05-16 at 22:40 -0500, olcott wrote:
>> On 5/16/2025 10:23 PM, wij wrote:
>>> On Fri, 2025-05-16 at 22:12 -0500, 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.
========== REMAINDER OF ARTICLE TRUNCATED ==========