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: This function proves that only the outermost HHH examines the
 execution trace
Date: Mon, 29 Jul 2024 21:33:37 +0200
Organization: A noiseless patient Spider
Lines: 146
Message-ID: <v88qqj$ju20$4@dont-email.me>
References: <v80h07$2su8m$3@dont-email.me> <v82bi4$39v6n$4@dont-email.me>
 <v82tr5$3dftr$2@dont-email.me> <v82vtl$3dq41$2@dont-email.me>
 <v830hg$3dftr$9@dont-email.me> <v83des$2nhr$1@news.muc.de>
 <v83dp3$3g9s7$1@dont-email.me> <v852m1$3sfas$1@dont-email.me>
 <v86loe$54o5$1@dont-email.me> <v87g9h$d073$1@dont-email.me>
 <v883of$g39i$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 29 Jul 2024 21:33:39 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="c0e8e7f3b0f9c9c9074b1b9f6672dea4";
	logging-data="653376"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19JmxbvEO54PfUqBh+6Ae6Z"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:f4YnEb+p34zR9Lp/4kI3MW60DSs=
In-Reply-To: <v883of$g39i$1@dont-email.me>
Content-Language: en-GB
Bytes: 7336

Op 29.jul.2024 om 14:59 schreef olcott:
> On 7/29/2024 2:27 AM, Mikko wrote:
>> On 2024-07-28 23:54:54 +0000, olcott said:
>>
>>> On 7/28/2024 4:23 AM, Mikko wrote:
>>>> On 2024-07-27 18:20:19 +0000, olcott said:
>>>>
>>>>> On 7/27/2024 1:14 PM, Alan Mackenzie wrote:
>>>>>> olcott <polcott333@gmail.com> wrote:
>>>>>>
>>>>>>> Stopping running is not the same as halting.
>>>>>>> DDD emulated by HHH stops running when its emulation has been 
>>>>>>> aborted.
>>>>>>> This is not the same as reaching its ret instruction and terminating
>>>>>>> normally (AKA halting).
>>>>>>
>>>>>> I think you're wrong, here.  All your C programs are a stand in for
>>>>>> turing machines.  A turing machine is either running or halted. 
>>>>>> There is
>>>>>> no third state "aborted".
>>>>>
>>>>> Until you take the conventional ideas of
>>>>> (a) UTM
>>>>> (b) TM Description
>>>>> (c) Decider
>>>>> and combine them together to become a simulating partial halt decider.
>>>>
>>>> You also need the conventional ideas of halting and halt decider.
>>>> The latter is largely a combination of the conventional ideas of
>>>> decider and halting but also involves the conventional of
>>>> prediction, so you need that, too.
>>>>
>>>> Although the conventional idea of testing is not relevant to the 
>>>> construction of a simulating partial halt decider it is helpful to 
>>>> presentation of the
>>>> result, especially if your target audience contains software 
>>>> engineers. If your target audience is mainly mathematicians the 
>>>> convnetional idea of proofs is more useful because in that case most 
>>>> of your presentation must be proofs.
>>>
>>> My ideas must be anchored in fully specified running software
>>> otherwise the false assumptions made by computer science people
>>> remain hidden.
>>
>> There is no "must" there. You may present your ideas whichever way you
>> think is the best for your purposes.
>>
> 
> Even when I make my ideas 100% concrete people still deny
> the verified facts.When I make them less than 100% concrete
> it is not as specific as verified facts.
> 
>> One good way to avoid false assumptions is to clearly state what is
>> assumed instead. Sometimes it may be necessary to clearly state what
>> is not assumed.
>>
>>> Even when I slap them in the face with proven facts they deny
>>> these proven facts on the basis of their indoctrination.
>>
>> Facts are never proven. They are observed.
>>
> 
> You didn't even bother to look at how HHH examines the
> execution trace of Infinite_Recursion() to determine that 
> Infinite_Recursion() specifies non-halting behavior.
> 
> Because of this you cannot see that the execution trace
> of DDD correctly emulated by DDD is essentially this same
> trace and thus also specifies non-halting behavior.
> 
> void Infinite_Recursion()
> {
>    Infinite_Recursion();
> }
> 
> _Infinite_Recursion()
> [0000215a] 55         push ebp      ; 1st line
> [0000215b] 8bec       mov ebp,esp   ; 2nd line
> [0000215d] e8f8ffffff call 0000215a ; 3rd line
> [00002162] 5d         pop ebp
> [00002163] c3         ret
> Size in bytes:(0010) [00002163]
> 
> Begin Local Halt Decider Simulation   Execution Trace Stored at:113934
> [0000215a][00113924][00113928] 55         push ebp      ; 1st line
> [0000215b][00113924][00113928] 8bec       mov ebp,esp   ; 2nd line
> [0000215d][00113920][00002162] e8f8ffffff call 0000215a ; 3rd line
> [0000215a][0011391c][00113924] 55         push ebp      ; 1st line
> [0000215b][0011391c][00113924] 8bec       mov ebp,esp   ; 2nd line
> [0000215d][00113918][00002162] e8f8ffffff call 0000215a ; 3rd line
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 
> =====
> 
> void DDD()
> {
>    HHH(DDD);
> }
> 
> _DDD()
> [00002177] 55               push ebp      ; 1st line
> [00002178] 8bec             mov ebp,esp   ; 2nd line
> [0000217a] 6877210000       push 00002177 ; push DDD
> [0000217f] e853f4ffff       call 000015d7 ; call HHH
> [00002184] 83c404           add esp,+04
> [00002187] 5d               pop ebp
> [00002188] c3               ret
> Size in bytes:(0018) [00002188]

The input for the simulator is DDD and all functions called by it, 
including HHH, which has conditional branch instructions.
So, it compares better with:

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

> 
> // executed HHH emulates 1st instance of DDD
> New slave_stack at:10388d
> Begin Local Halt Decider Simulation   Execution Trace Stored at:113895
> [00002177][00113885][00113889] 55         push ebp      ; 1st line
> [00002178][00113885][00113889] 8bec       mov ebp,esp   ; 2nd line
> [0000217a][00113881][00002177] 6877210000 push 00002177 ; push DDD
> [0000217f][0011387d][00002184] e853f4ffff call 000015d7 ; call HHH

Olcott is cheating. He hides that the call instruction should be 
followed by the instructions of HHH according to the semantics of the 
x86 language. HHH has conditional branch instructions.

> 
> // emulated HHH emulates 2nd instance of DDD
> New slave_stack at:14e2b5
> [00002177][0015e2ad][0015e2b1] 55         push ebp      ; 1st line
> [00002178][0015e2ad][0015e2b1] 8bec       mov ebp,esp   ; 2nd line
> [0000217a][0015e2a9][00002177] 6877210000 push 00002177 ; push DDD
> [0000217f][0015e2a5][00002184] e853f4ffff call 000015d7 ; call HHH

Olcott is cheating. He hides that the call instruction should be 
followed by the instructions of HHH according to the semantics of the 
x86 language. HHH has conditional branch instructions.

> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
> 

Invalid decision. Only two recursions detected. Two is not infinite.