Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: olcott <polcott333@gmail.com>
Newsgroups: comp.theory
Subject: HHH(DDD) sees the exact same behavior pattern as
 HHH(Infinite_Recursion)
Date: Sun, 28 Jul 2024 09:25:53 -0500
Organization: A noiseless patient Spider
Lines: 164
Message-ID: <v85kdi$3v9fb$2@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>
 <KUidnalBUcYWDjj7nZ2dnZfqn_ednZ2d@brightview.co.uk>
 <v84d5a$3p1o0$1@dont-email.me> <v84tpk$3rc90$2@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sun, 28 Jul 2024 16:25:54 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e780778616be4582a0134c2484eeadc2";
	logging-data="4171243"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+sEj6g34ZJiUzB2JmOmjrT"
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:nL8Mixv7cpWkhvxN/Fwg52KKstQ=
In-Reply-To: <v84tpk$3rc90$2@dont-email.me>
Content-Language: en-US
Bytes: 8464

On 7/28/2024 2:59 AM, Fred. Zwarts wrote:
> Op 28.jul.2024 om 05:15 schreef olcott:
>> On 7/27/2024 7:40 PM, Mike Terry wrote:
>>> On 27/07/2024 19:14, 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".  An aborted C program certainly doesn't
>>>> correspond with a running turing machine - so it must be a halted 
>>>> turing
>>>> machine.
>>>>
>>>> So aborted programs are halted programs.  If you disagree, perhaps you
>>>> could point out where in my arguments above I'm wrong.
>>>>
>>>
>>> Aborting is an action performed by a simulator, not the TM being 
>>> simulated.
>>>
>>> If we want to count "aborted" as some kind of final status, it will 
>>> have to be the status of a specific /PARTIAL SIMULATOR's/ simulation 
>>> of a given computation.  That's not a property of the computation 
>>> itself, as different partial simulators can simulate the same 
>>> computation and terminate for different reasons.  Like HHH(DDD) 
>>> aborts, while UTM(DDD) simulates to completion and so the final 
>>> simulation status is halts. [Neither of those outcomes contradict the 
>>> fact that the computation DDD() halts.]
>>>
>>> If some partial simulator halts when simulating a computation [as 
>>> with UTM(DDD)] that implies the computation DDD() halts.  But if the 
>>> simulator aborts, it doesn't say that much (in and of itself) about 
>>> whether the /computation/ halts.  The halting problem statement is 
>>> not concerned with simulations or how the simulations end.
>>>
>>> Every time anyone in these PO threads says "halts" it ought to be 
>>> 100% clear to everyone whether the computation itself is being 
>>> discussed, or whether some simulation final status is intended.  (But 
>>> that's far from being the case!)  Since the halting problem is 
>>> concerned with computations halting and not how partial simulations 
>>> are ended, I suggest that PO explicitly make clear that he is 
>>> referring to simulations, whenever that is the case.  It seems 
>>> reasonable that readers seeing "halts" with no further clarification 
>>> can interpret that as actual computation behaviour, as that is how 
>>> the term is always used in the literature.  Same with other terms 
>>> like "reach"...
>>>
>>> So when PO says "DDD simulated by HHH cannot reach its final ret 
>>> instruction" is he talking about the computation DDD() [as defined 
>>> mathematically], or its simulation by HHH?  He means the latter, but 
>>> its far from clear, I'd say!  [I think most readers now have come 
>>> around to reading it as a statement about simulations rather than the 
>>> actual computation, which totally changes things...]
>>>
>>>
>>> Mike.
>>>
>>
>> _DDD()
>> [00002163] 55         push ebp      ; housekeeping
>> [00002164] 8bec       mov ebp,esp   ; housekeeping
>> [00002166] 6863210000 push 00002163 ; push DDD
>> [0000216b] e853f4ffff call 000015c3 ; call HHH(DDD)
>> [00002170] 83c404     add esp,+04
>> [00002173] 5d         pop ebp
>> [00002174] c3         ret
>> Size in bytes:(0018) [00002174]
>>
>> It is a verified fact that DDD emulated by HHH 100% exactly
>> and precisely according to the actual x86 semantics of
>> the emulated code including the recursive call that causes
>> HHH to emulate itself emulating DDD cannot possibly get
>> past it own 0000216b machine address.
>>
>> *Anyone as much as hinting otherwise is not being truthful*
>> If we remove all of the problematic code then this same
>> trace still occurs until it crashes from OOM error.
>>
> 
> No matter how much olcott wants it to be correct, or how many times 
> olcott repeats that it is correct, it does not change the fact that such 
> a simulation is incorrect, because it is unable to reach the end.

It is ridiculously stupid to expect the correct emulation
of a non-halting input to end.

This is the exact same pattern with Infinite_Recursion()
where there are no conditional branch instructions that
would prevent the first three instructions of
Infinite_Recursion() from endlessly repeating.


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

If you cannot see that the above x86 machine code proves that
it will never halt then you can't possibly understand what I
have been saying.

The first three lines of _Infinite_Recursion() repeat and there
are no conditional branch in that sequence that can possibly keep
it from repeating forever. This exact same pattern is shown below.

=====

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]

// 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

// 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
Local Halt Decider: Infinite Recursion Detected Simulation Stopped



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