Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Mon, 19 May 2025 13:44:21 +0300
Organization: -
Lines: 226
Message-ID: <100f225$1j18n$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> <100aolc$hq2u$1@dont-email.me> <943f3512f1c253f770eb41519145d4159c0cd6aa.camel@gmail.com> <100dhiv$167g2$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 19 May 2025 12:44:21 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="8f4381c44869abbb66b062db77a9c084";
	logging-data="1672471"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18+vAFaDQRN16EwHWnkgJRo"
User-Agent: Unison/2.2
Cancel-Lock: sha1:jDeHn/BLC0n7hjf+ROjow4ha7Z8=

On 2025-05-18 20:57:03 +0000, olcott said:

> 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 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 
========== REMAINDER OF ARTICLE TRUNCATED ==========