Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Sat, 17 May 2025 20:46:23 +0100
Organization: A noiseless patient Spider
Lines: 190
Message-ID: <100ap2g$i1dj$1@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>
 <100a7e4$efgi$1@dont-email.me>
 <f94f006b40c3ca204d41be9b4507280a3a4fc17b.camel@gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 17 May 2025 21:46:26 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="7e4f67ee19a027ba8df965182a825f7b";
	logging-data="591283"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX192BNs4rmh3xDM5miKnnA4K10XC7EJ1UPw="
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
Cancel-Lock: sha1:xdowWVMHpv9PGAgRIUknucSGZXY=
In-Reply-To: <f94f006b40c3ca204d41be9b4507280a3a4fc17b.camel@gmail.com>

On 17/05/2025 20:26, 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 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.
>>
>> Eh?� The f was something /you/ introduced!� You said it represents some computation which UTM U
>> simulates.� How can f suddenly become undefined after you defined it?
>>
>> Do you mean that f would not be on the input tape for (outer)U?� That's not the case at all.� In
>> U(f), the input tape for U contains a representation of f.� When (outer)U simulates (inner)U
>> simulating f, (outer)U's tape contains a representation of computation U(f), which internally
>> contains the original representation of f.� The f is still there and equally well defined in
>> U(U(f)).
>>
>> I think you would benefit from being more explicit and generally more careful in your notation!
>>
>> Using notation <P,I> to mean U's input tape representation of "TM P, running with input I":
>>
>>  ��� Your U(f)����� is U(<fp,fi>)		// fp = TM(f), fi=InputTape(f)
>>  ��� Your U(U(f))�� is U((<U,<fp,fi>>)
>>
>> f is still there!� It has not become "undefined".
>>
========== REMAINDER OF ARTICLE TRUNCATED ==========