Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Fred. Zwarts" <F.Zwarts@HetNet.nl>
Newsgroups: comp.theory
Subject: Re: Defining a correct simulating halt decider
Date: Tue, 3 Sep 2024 09:15:17 +0200
Organization: A noiseless patient Spider
Lines: 73
Message-ID: <vb6d25$38dum$2@dont-email.me>
References: <vb4plc$2tqeg$1@dont-email.me> <vb4u1g$2u7sn$4@dont-email.me>
 <vb5drq$30qlu$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 03 Sep 2024 09:15:17 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="213ea51a05a743f3af7fc7781befc3df";
	logging-data="3422166"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18KUlksehgq+uZNZ3StFW/a"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:Zr7UY2WdlDJZgh5DZplSfkxbASA=
In-Reply-To: <vb5drq$30qlu$1@dont-email.me>
Content-Language: en-GB
Bytes: 4036

Op 03.sep.2024 om 00:22 schreef olcott:
> On 9/2/2024 12:52 PM, Fred. Zwarts wrote:
>> Op 02.sep.2024 om 18:38 schreef olcott:
>>> A halt decider is a Turing machine that computes
>>> the mapping from its finite string input to the
>>> behavior that this finite string specifies.
>>>
>>> If the finite string machine string machine
>>> description specifies that it cannot possibly
>>> reach its own final halt state then this machine
>>> description specifies non-halting behavior.
>>>
>>> A halt decider never ever computes the mapping
>>> for the computation that itself is contained within.
>>>
>>> Unless there is a pathological relationship between
>>> the halt decider H and its input D the direct execution
>>> of this input D will always have identical behavior to
>>> D correctly simulated by simulating halt decider H.
>>>
>>> *Simulating Termination Analyzer H Not Fooled by Pathological Input D*
>>> https://www.researchgate.net/ 
>>> publication/369971402_Simulating_Termination_Analyzer_H_is_Not_Fooled_by_Pathological_Input_D
>>>
>>> A correct emulation of DDD by HHH only requires that HHH
>>> emulate the instructions of DDD** including when DDD calls
>>> HHH in recursive emulation such that HHH emulates itself
>>> emulating DDD.
>>
>> Indeed, it should simulate *itself* and not a hypothetical other HHH 
>> with different behaviour.
>> If HHH includes code to see a 'special condition' and aborts and 
>> halts, then it should also simulate the HHH that includes this same 
>> code and 
> 
> 
> DDD has itself and the emulated HHH stuck in recursive emulation.
> 
> void DDD()
> {
>    HHH(DDD);
>    return;
> }

It is not DDD. It is HHH that has the problem when trying to simulate 
itself.

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

Only when HHH would not abort (as in olcott's dream) there would be an 
infinite recursion. But for the HHH that aborts, it is stuck in the 
recursion for only a few recursions. Then it aborts and halts.


> 
> When HHH emulates itself emulating DDD the emulated
> HHH cannot possibly return because each DDD keeps
> calling HHH to emulate itself again until the outer
> executed HHH kills the whole emulated process at
> the very first emulated DDD before it ever reaches
> its own second line.
And this outer HHH does it one cycle before the inner HHH would do the 
same and halt. This means that the outer HHH misses the halting 
behaviour of the inner HHH by aborting too soon.
In this way the outer HHH prevents the inner HHH to reach the end of the 
simulation. The outer HHH, therefore, violates the semantics of the x86 
language, by skipping the last few instructions of the halting program.
But olcott is still dreaming of the inner HHH that does not abort and 
thinks that the abort code only affects the outer HHH, not the inner 
HHH. A beginners error to think that a code change will not affect the 
behaviour of a program.