Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott2@gmail.com>
Newsgroups: comp.theory,sci.logic
Subject: Re: Proof that H(D,D) meets its abort criteria
Date: Fri, 15 Mar 2024 14:14:25 -0500
Organization: A noiseless patient Spider
Lines: 110
Message-ID: <ut26mi$2e06s$5@dont-email.me>
References: <ut1sgk$2buev$2@dont-email.me> <ut20uf$1vtvi$1@i2pn2.org>
 <ut21t3$2d19j$1@dont-email.me> <ut24j0$2dnbk$2@dont-email.me>
 <ut24kj$2djbv$5@dont-email.me> <ut2675$1vtvj$9@i2pn2.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 15 Mar 2024 19:14:26 -0000 (UTC)
Injection-Info: dont-email.me; posting-host="628c0b780d2c261756f82ddadd066eb3";
	logging-data="2556124"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18sH6XjA5AwFC94gjFx39HH"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:/NtShO1T31E0kEHFuIh3HLcqHnA=
In-Reply-To: <ut2675$1vtvj$9@i2pn2.org>
Content-Language: en-US
Bytes: 6205

On 3/15/2024 2:06 PM, Richard Damon wrote:
> On 3/15/24 11:39 AM, olcott wrote:
>> On 3/15/2024 1:38 PM, immibis wrote:
>>> On 15/03/24 18:52, olcott wrote:
>>>> On 3/15/2024 12:36 PM, Richard Damon wrote:
>>>>> On 3/15/24 9:20 AM, olcott wrote:
>>>>>> Best selling author of Theory of Computation textbooks:
>>>>>> *Introduction To The Theory Of Computation 3RD, by sipser*
>>>>>> https://www.amazon.com/Introduction-Theory-Computation-Sipser/dp/8131525295/
>>>>>>
>>>>>> Date 10/13/2022 11:29:23 AM
>>>>>> *MIT Professor Michael Sipser agreed this verbatim paragraph is 
>>>>>> correct*
>>>>>> (He has neither reviewed nor agreed to anything else in this paper)
>>>>>> (a) 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
>>>>>> (b) H can abort its simulation of D and correctly report that D 
>>>>>> specifies a non-halting sequence of configurations.
>>>>>>
>>>>>> *When we apply the abort criteria* (elaborated above)
>>>>>> Will you halt if you never abort your simulation?
>>>>>> *Then H(D,D) is proven to meet this criteria*
>>>>>>
>>>>>> *Proof that H(D,D) meets its abort criteria*
>>>>>>
>>>>>> int D(int (*x)())
>>>>>> {
>>>>>>    int Halt_Status = H(x, x);
>>>>>>    if (Halt_Status)
>>>>>>      HERE: goto HERE;
>>>>>>    return Halt_Status;
>>>>>> }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>    Output("Input_Halts = ", H(D,D));
>>>>>> }
>>>>>>
>>>>>>   machine   stack     stack     machine    assembly
>>>>>>   address   address   data      code       language
>>>>>>   ========  ========  ========  =========  =============
>>>>>> [00001d22][00102fc9][00000000] 55         push ebp      ; begin 
>>>>>> main()
>>>>>> [00001d23][00102fc9][00000000] 8bec       mov ebp,esp
>>>>>> [00001d25][00102fc5][00001cf2] 68f21c0000 push 00001cf2 ; push DD
>>>>>> [00001d2a][00102fc1][00001cf2] 68f21c0000 push 00001cf2 ; push D
>>>>>> [00001d2f][00102fbd][00001d34] e8eef7ffff call 00001522 ; call H(D,D)
>>>>>>
>>>>>> H: Begin Simulation   Execution Trace Stored at:113075
>>>>>> Address_of_H:1522
>>>>>> [00001cf2][00113061][00113065] 55         push ebp       ; enter D(D)
>>>>>> [00001cf3][00113061][00113065] 8bec       mov ebp,esp
>>>>>> [00001cf5][0011305d][00103031] 51         push ecx
>>>>>> [00001cf6][0011305d][00103031] 8b4508     mov eax,[ebp+08]
>>>>>> [00001cf9][00113059][00001cf2] 50         push eax       ; push D
>>>>>> [00001cfa][00113059][00001cf2] 8b4d08     mov ecx,[ebp+08]
>>>>>> [00001cfd][00113055][00001cf2] 51         push ecx       ; push D
>>>>>> [00001cfe][00113051][00001d03] e81ff8ffff call 00001522  ; call 
>>>>>> H(D,D)
>>>>>> H: Recursive Simulation Detected Simulation Stopped
>>>>>>                            H(D,D) returns 0 to main()
>>>>>>
>>>>>> *That was proof that H(D,D) meets its abort criteria*
>>>>>> H(D,D) correctly determines that itself is being called with its 
>>>>>> same inputs and there are no conditional branch instructions 
>>>>>> between the invocation of D(D) and its call to H(D,D).
>>>>>>
>>>>>>
>>>>>
>>>>> Except that D calling H(D,D) does NOT prove the required (a), since 
>>>>> the simulated D WILL stop running because *ITS* H will abort *ITS* 
>>>>> simulation and returm 0 so that simulated D will halt.
>>>> You keep saying that H(D,D) never really needs to abort the
>>>> simulation of its input because after H(D,D) has aborted the
>>>> simulation of this input it no longer needs to be aborted.
>>>>
>>> You keep thinking there is more than one H(D,D) and then when it's 
>>> convenient for you you think there is only one H(D,D). Why is that?
>>
>> The first H(D,D) to see that the abort criteria has been met
>> (the outermost one) must abort the simulation of its input or
>> none of them ever abort.
>>
> 
> But since it does, which is your definition of H, the others 

never begin to be simulated.

> do, so THIS 
> algorithm for H doesn't NEED to, but does.
> 

H(D,D) cannot simply wait for another instance of itself to do something
otherwise all instances of H are waiting on the next one.

> The input doesn't actually "refer" to this outer H, but just happen to 
> be copies (at least if you are going to claim to be the equivalent of 
> the linz H / H^ system), you can't tie the various version running into 
> a single identity.
> 
> If you try to define the H in D to be actually REFERING to the same H, 
> and not just an optimization to help realizability, then you run into 
> the problem that you have left the equivalence to that which you want to 
> claim, and thus your whole argument is invalid.

-- 
Copyright 2024 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer