Path: ...!eternal-september.org!feeder3.eternal-september.org!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: Wed, 21 May 2025 11:47:27 +0300
Organization: -
Lines: 89
Message-ID: <100k3uv$2ojv4$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> <10055rn$37m1t$1@dont-email.me> <1006pc9$3ld84$1@dont-email.me> <1007m9e$3qb7l$17@dont-email.me> <100f1oi$1iukq$1@dont-email.me> <100jli8$2m26r$3@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 10:47:27 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e8199b24f794f763c658a0f941a1cc48";
	logging-data="2904036"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18wDh2f3NQ6Mi1wdTtTGJhR"
User-Agent: Unison/2.2
Cancel-Lock: sha1:GhUDWWpcSQTqSgCEkTJVBpT8+Kk=
Bytes: 4438

On 2025-05-21 04:41:44 +0000, olcott said:

> On 5/19/2025 5:39 AM, Mikko wrote:
>> On 2025-05-16 15:40:29 +0000, olcott said:
>> 
>>> On 5/16/2025 2:27 AM, Mikko wrote:
>>>> On 2025-05-15 16:47:49 +0000, olcott said:
>>>> 
>>>>> On 5/15/2025 11:08 AM, 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.
>>>>> 
>>>>> These things cannot be investigated in great
>>>>> depth because there is no fully encoded UTM in
>>>>> any standard language.
>>>> 
>>>> Investigations do not need a standard language. For an investigation an
>>>> ad hoc language is good enough and usually better.
>>> 
>>> Until I made this concrete people kept assuming that
>>> an input DD could be defined that actually does the
>>> opposite of whatever value that its simulating termination
>>> analyzer HHH returns.
>> 
>> That need not and should not be assumed. That can be constructively
>> proven.
>> 
>> Which doesn't matter to any investigation.
> 
> There are only two ways to try to define a DD
> that actually does the opposition of whatever
> value that is termination analyzer returns.

One way is enough. The way used by e.g. Linz does work.

But that is irrelevant both to the your above claim that
> These things cannot be investigated in great
> depth because there is no fully encoded UTM in
> any standard language.
and to my response to that claim.

Apparently you don't know enough about investigations and languages
to say anything sensible about them.

-- 
Mikko