Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: sci.logic
Subject: Re: How the requirements that Professor Sipser agreed to are exactly met
Date: Sun, 18 May 2025 13:40:32 +0300
Organization: -
Lines: 63
Message-ID: <100cdf0$utk1$1@dont-email.me>
References: <vvte01$14pca$29@dont-email.me> <vvut31$1mfgr$1@dont-email.me> <vvviu7$1rc7v$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 18 May 2025 12:40:32 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="db593b51986ab1c7ad0e4311e24c5f65";
	logging-data="1013377"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+P1hvQpoOgLoVMaiO+jswj"
User-Agent: Unison/2.2
Cancel-Lock: sha1:WDqn+dwaDPO1PkMYTLPpg6hQHMM=

On 2025-05-13 13:54:15 +0000, olcott said:

> On 5/13/2025 2:41 AM, Mikko wrote:
>> On 2025-05-12 18:17:37 +0000, olcott said:
>> 
>>> Introduction to the Theory of Computation 3rd Edition
>>> by Michael Sipser (Author)
>>> 4.4 out of 5 stars    568 rating
>>> 
>>> https://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/ 
>>> dp/113318779X
>>> 
>>> int DD()
>>>   {
>>>    int Halt_Status = HHH(DD);
>>>    if (Halt_Status)
>>>      HERE: goto HERE;
>>>    return Halt_Status;
>>>   }
>>> 
>>> DD correctly simulated by any pure simulator
>>> named HHH cannot possibly terminate thus proving
>>> that this criteria has been met:
>>> 
>>> <MIT Professor Sipser agreed to ONLY these verbatim words 10/13/2022>
>>>      If simulating halt decider H correctly simulates its
>>>      input D until H correctly determines that its simulated D
>>>      would never stop running unless aborted then
>> 
>> This specifies two requirements:
>> 1. H correctly simulates that part of the behaviour of D that starts
>> from the start of the execution and does not end before the second
>> requirement is satisfied.
>> 2. H correctly determines that unsimulated part of the behaviour is
>> infinitely long.
>> 
>> The second reuirement is not satisfied when HHH analyses the above
>> DD.
> 
> In other words you believe that DD will halt
> on its own without ever being aborted by HHH.
> That is counter-factual.

I didn't say so. If HHH does not return zero then DD does not halt.
I said that your HHH, unlike some other partial halt deciders, fails
to analyze DD enough to correctly determine whether it halts.

> _DD()
> [00002133] 55         push ebp      ; housekeeping
> [00002134] 8bec       mov ebp,esp   ; housekeeping
> [00002136] 51         push ecx      ; make space for local
> [00002137] 6833210000 push 00002133 ; push DD
> [0000213c] e882f4ffff call 000015c3 ; call HHH(DD)
> ...
> 
> HHH determines that DD correctly simulated by
> HHH keeps calling HHH(DD)

which in reality does not happen as DD calls HHH only once.

-- 
Mikko