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: DDD correctly emulated by HHH is correctly rejected as
 non-halting.
Date: Fri, 12 Jul 2024 16:22:27 +0200
Organization: A noiseless patient Spider
Lines: 100
Message-ID: <v6re73$32501$1@dont-email.me>
References: <v6m7si$1uq86$2@dont-email.me> <v6mhc7$20hbo$2@dont-email.me>
 <v6mhr3$20kkr$2@dont-email.me> <v6nts5$2be3m$1@dont-email.me>
 <v6op4h$2fuva$4@dont-email.me> <v6qo1d$2ugov$1@dont-email.me>
 <v6rajl$30qtt$7@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 12 Jul 2024 16:22:27 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="7af5eacf7ee35a6bd95a47fb26ac0889";
	logging-data="3216385"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX191ZOUKGhiu8OPOymkW/xcD"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:eY/gimFt4de0NAmg7E7Os/tVhFY=
In-Reply-To: <v6rajl$30qtt$7@dont-email.me>
Content-Language: en-GB
Bytes: 4506

Op 12.jul.2024 om 15:20 schreef olcott:
> On 7/12/2024 3:03 AM, Mikko wrote:
>> On 2024-07-11 14:10:24 +0000, olcott said:
>>
>>> On 7/11/2024 1:25 AM, Mikko wrote:
>>>> On 2024-07-10 17:53:38 +0000, olcott said:
>>>>
>>>>> On 7/10/2024 12:45 PM, Fred. Zwarts wrote:
>>>>>> Op 10.jul.2024 om 17:03 schreef olcott:
>>>>>>> typedef void (*ptr)();
>>>>>>> int HHH(ptr P);
>>>>>>>
>>>>>>> void DDD()
>>>>>>> {
>>>>>>>    HHH(DDD);
>>>>>>> }
>>>>>>>
>>>>>>> int main()
>>>>>>> {
>>>>>>>    HHH(DDD);
>>>>>>> }
>>>>>>
>>>>>> Unneeded complexity. It is equivalent to:
>>>>>>
>>>>>>        int main()
>>>>>>        {
>>>>>>          return HHH(main);
>>>>>>        }
>>>>>>
>>>>>
>>>>>
>>>>> Every time any HHH correctly emulates DDD it calls the
>>>>> x86utm operating system to create a separate process
>>>>> context with its own memory virtual registers and stack,
>>>>> thus each recursively emulated DDD is a different instance.
>>>>
>>>> However, each of those instances has the same sequence of instructions
>>>> that the x86 language specifies the same operational meaning.
>>>>
>>>
>>> *That is counter-factual*
>>> When DDD is correctly emulated by HHH according to the
>>> semantics of the x86 programming language HHH must abort
>>> its emulation of DDD or both HHH and DDD never halt.
>>
>> There is not "must" anywhere in the semantics of the programming 
>> language.
>>
> 
> The semantics of the language specifies the behavior of
> the machine code thus deriving the must.

The x86 language does not specify that an abort must be done for a 
halting program. If the simulation of an aborting simulator was not 
aborted, it would halt, according to the x86 language.
This shows that HHH does not follow the semantics of the x86 language.
> 
>>> When DDD is correctly emulated by HHH1 according to the
>>> semantics of the x86 programming language HHH1 need not
>>> abort its emulation of DDD because HHH has already done this.
>>
>> However, the program DDD is the same in both cases and therefore the
>> its behavioral meaning per x86 semantics is also the same.
>>
> 
> HHH1(DDD) only halts because HHH(DDD) aborts its emulation
> thus proving the the behaviors are different.

No, it proves that HHH1's simulation is correct, whereas HHH's 
simulation is incorrect, because HHH aborts one cycle too soon.
It proves that HHH cannot possibly simulate itself correctly.

> 
>>> The behavior of DDD emulated by HHH1 is identical to the
>>> behavior of the directly executed DDD().
>>
>> Which is the behaviour of DDD accordint to the semantics of x86 language.
>>
> 
> If you stupidly ignore that DDD does call HHH in recursive
> emulation it might superfically seem that way.
> 

DDD has nothing to do with it. It is easy to eliminate DDD:

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

This has the same problem. Proving that the problem is not in DDD, but 
in HHH, which is required to halt, but it decides that HHH does not halt.

HHH is unable to decide about finite recursions.

void Finite_Recursion (int N) {
   if (N > 0) Finite_Recursion (N - 1);
}

It decides after two recursions that there is an infinite recursion, 
which is incorrect.