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,sci.logic
Subject: Re: DD correctly simulated by HH --- never stops running without
 aborting its simulation
Date: Fri, 7 Jun 2024 15:58:52 +0200
Organization: A noiseless patient Spider
Lines: 153
Message-ID: <v3v3mu$236ut$1@dont-email.me>
References: <v3svh3$1k5vr$1@dont-email.me> <v3uen8$1vn0h$1@dont-email.me>
 <v3v1gf$22vrk$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 07 Jun 2024 15:58:55 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="5bcde24dcfe9ee81a0f51067fa74cb7b";
	logging-data="2202589"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19ZAPz4E8NPCuUTsC+sM6Vr"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:XV/lB8cCnK93yXNdub81RY5A+pY=
Content-Language: en-GB
In-Reply-To: <v3v1gf$22vrk$2@dont-email.me>
Bytes: 7762

Op 07.jun.2024 om 15:21 schreef olcott:
> On 6/7/2024 3:00 AM, Fred. Zwarts wrote:
>> Op 06.jun.2024 om 20:35 schreef olcott:
>>> <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
>>>
>>>    H can abort its simulation of D and correctly report that D
>>>    specifies a non-halting sequence of configurations.
>>> </MIT Professor Sipser agreed to ONLY these verbatim words10/13/2022>
>>>
>>> *Try to show how this DD correctly simulated by any HH ever*
>>> *stops running without having its simulation aborted by HH*
>>>
>>> _DD()
>>> [00001e12] 55         push ebp
>>> [00001e13] 8bec       mov  ebp,esp
>>> [00001e15] 51         push ecx
>>> [00001e16] 8b4508     mov  eax,[ebp+08]
>>> [00001e19] 50         push eax      ; push DD
>>> [00001e1a] 8b4d08     mov  ecx,[ebp+08]
>>> [00001e1d] 51         push ecx      ; push DD
>>> [00001e1e] e85ff5ffff call 00001382 ; call HH
>>>
>>
>> Olcott has proven himself that HH reports false negatives, with the 
>> following example:
>>
>>         typedef int (*ptr)();  // ptr is pointer to int function in C
>>
>>         int H(ptr p, ptr i);
>>
>>         int main()
>>         {
>>           return H(main, 0);
>>         }
>>
>> He proved that main halts and that H reports non-halting.
>>
> 
> main() does meet the Sipser approved criteria and you cannot
> possibly show otherwise.
> 
>     If simulating halt decider HH correctly simulates its input main
>     until HH correctly determines that its simulated main would never
>     stop running unless aborted then
> 
> _main()
> [00001e42] 55         push ebp
> [00001e43] 8bec       mov ebp,esp
> [00001e45] 6a00       push +00
> [00001e47] 68421e0000 push 00001e42
> [00001e4c] e831f5ffff call 00001382
> [00001e51] 83c408     add esp,+08
> [00001e54] 50         push eax
> [00001e55] 6843070000 push 00000743
> [00001e5a] e843e9ffff call 000007a2
> [00001e5f] 83c408     add esp,+08
> [00001e62] eb79       jmp 00001edd
> [00001e64] 6a05       push +05
> [00001e66] 68321d0000 push 00001d32
> [00001e6b] e8f2f6ffff call 00001562
> [00001e70] 83c408     add esp,+08
> [00001e73] 50         push eax
> [00001e74] 6853070000 push 00000753
> [00001e79] e824e9ffff call 000007a2
> [00001e7e] 83c408     add esp,+08
> [00001e81] 68621d0000 push 00001d62
> [00001e86] e8d7f9ffff call 00001862
> [00001e8b] 83c404     add esp,+04
> [00001e8e] 50         push eax
> [00001e8f] 6863070000 push 00000763
> [00001e94] e809e9ffff call 000007a2
> [00001e99] 83c408     add esp,+08
> [00001e9c] 6a05       push +05
> [00001e9e] 68f21c0000 push 00001cf2
> [00001ea3] e8baf6ffff call 00001562
> [00001ea8] 83c408     add esp,+08
> [00001eab] 50         push eax
> [00001eac] 6873070000 push 00000773
> [00001eb1] e8ece8ffff call 000007a2
> [00001eb6] 83c408     add esp,+08
> [00001eb9] 68e21d0000 push 00001de2
> [00001ebe] 68e21d0000 push 00001de2
> [00001ec3] e89af6ffff call 00001562
> [00001ec8] 83c408     add esp,+08
> [00001ecb] 50         push eax
> [00001ecc] 6883070000 push 00000783
> [00001ed1] e8cce8ffff call 000007a2
> [00001ed6] 83c408     add esp,+08
> [00001ed9] 33c0       xor eax,eax
> [00001edb] eb02       jmp 00001edf
> [00001edd] 33c0       xor eax,eax
> [00001edf] 5d         pop ebp
> [00001ee0] c3         ret
> Size in bytes:(0159) [00001ee0]
> 
>   machine   stack     stack     machine    assembly
>   address   address   data      code       language
>   ========  ========  ========  =========  =============
> [00001e42][00103375][00000000] 55         push ebp
> [00001e43][00103375][00000000] 8bec       mov ebp,esp
> [00001e45][00103371][00000000] 6a00       push +00
> [00001e47][0010336d][00001e42] 68421e0000 push 00001e42 ; push main
> [00001e4c][00103369][00001e51] e831f5ffff call 00001382 ; call HH
> New slave_stack at:103419
> 
> Begin Local Halt Decider Simulation   Execution Trace Stored at:113421
> [00001e42][0011340d][00113411] 55         push ebp
> [00001e43][0011340d][00113411] 8bec       mov ebp,esp
> [00001e45][00113409][00000000] 6a00       push +00
> [00001e47][00113405][00001e42] 68421e0000 push 00001e42 ; push main
> [00001e4c][00113401][00001e51] e831f5ffff call 00001382 ; call HH
> New slave_stack at:14de41
> [00001e42][0015de35][0015de39] 55         push ebp
> [00001e43][0015de35][0015de39] 8bec       mov ebp,esp
> [00001e45][0015de31][00000000] 6a00       push +00
> [00001e47][0015de2d][00001e42] 68421e0000 push 00001e42 ; push main
> [00001e4c][0015de29][00001e51] e831f5ffff call 00001382 ; call HH
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 
> [00001e51][00103375][00000000] 83c408     add esp,+08
> [00001e54][00103371][00000000] 50         push eax
> [00001e55][0010336d][00000743] 6843070000 push 00000743
> [00001e5a][0010336d][00000743] e843e9ffff call 000007a2
> Input_Halts = 0
> [00001e5f][00103375][00000000] 83c408     add esp,+08
> [00001e62][00103375][00000000] eb79       jmp 00001edd
> [00001edd][00103375][00000000] 33c0       xor eax,eax
> [00001edf][00103379][00000018] 5d         pop ebp
> [00001ee0][0010337d][00000000] c3         ret
> Number of Instructions Executed(11357) == 170 Pages
> 
> 

You showed the proof for the false negative already somewhat earlier. No 
need to repeat it.
Also the fact that Sipser agreed that there is a good explanation for 
the false negative, was mentioned by you before.

We also know that you do not claim that the decider H reports on real 
behaviour (direct execution), but about its own simulation.
That is a subtle difference, just as in these two sentences:
a) main is non-halting.
b) H's decision is that main is non-halting.

It is clear that b can be true, even if a is false, because it remains 
H's decision. Your claims come down to that H's decision is about b, not 
a. Then, of course, H decision is trivially correct.
So, false negatives should not bother you.

(But then H's decision is completely uninteresting for most people.)