Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: How to write a self-referencial TM?
Date: Mon, 19 May 2025 10:21:16 +0200
Organization: A noiseless patient Spider
Lines: 80
Message-ID: <100eplt$1h83t$2@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>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 19 May 2025 10:21:18 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="f26a1aee18951468acd4cabd87ed5208";
	logging-data="1613949"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19q8Q6LHf0dWgxJG+EH1Cbc"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:ZFnztFXy4Vd1SSb7Pn5PS+UvdKA=
In-Reply-To: <1007m9e$3qb7l$17@dont-email.me>
Content-Language: nl, en-GB
Bytes: 3991

Op 16.mei.2025 om 17:40 schreef olcott:
> 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.
> 
> int main()
> {
>    DD(); // HHH cannot report on the behavior of its caller.
> }
> 

HHH cannot simulate itself. It is programmed to do a wild guess about 
its own behaviour. Therefore, it produces false negatives. It reports 
non-halting when it halts:

        int main() {
          return HHH(main);
        }