Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.software-eng > #3488

Re: Refuting the HP proofs (adapted for software engineers)

Cross-posted to 4 groups.

Show all headers | View raw

On Fri, 3 Jun 2022 17:17:12 -0500
olcott <NoOne@NoWhere.com> wrote:

> This post assumes that you already know my work, otherwise please
> read the linked paper provided below. This work is based on the
> x86utm operating system that was created so that every detail of the
> halting problem could be directly examined in C/x86.
> 
> void Infinite_Loop()
> {
>    HERE: goto HERE;
> }
> 
> int main()
> {
>    Output("Input_Halts = ", H0(Infinite_Loop));
> }
> 
> _Infinite_Loop()
> [00001342](01)  55              push ebp
> [00001343](02)  8bec            mov ebp,esp
> [00001345](02)  ebfe            jmp 00001345
> [00001347](01)  5d              pop ebp
> [00001348](01)  c3              ret
> Size in bytes:(0007) [00001348]
> 
> It is totally obvious that the _Infinite_Loop() would never halt 
> (meaning that it terminates normally by reaching its "ret"
> instruction).
> 
> Equally obvious is the fact that a partial x86 emulation of this
> input conclusively proves that its complete x86 emulation would never
> halt.
> 
> Begin Local Halt Decider Simulation   Execution Trace Stored at:212343
> [00001342][00212333][00212337] 55         push ebp
> [00001343][00212333][00212337] 8bec       mov ebp,esp
> [00001345][00212333][00212337] ebfe       jmp 00001345
> [00001345][00212333][00212337] ebfe       jmp 00001345
> Local Halt Decider: Infinite Loop Detected Simulation Stopped
> 
> The exact same reasoning applies to the correctly emulated input to
> H(P,P):
> 
> _P()
> [00001352](01)  55              push ebp
> [00001353](02)  8bec            mov ebp,esp
> [00001355](03)  8b4508          mov eax,[ebp+08]
> [00001358](01)  50              push eax      // push P
> [00001359](03)  8b4d08          mov ecx,[ebp+08]
> [0000135c](01)  51              push ecx      // push P
> [0000135d](05)  e840feffff      call 000011a2 // call H
> [00001362](03)  83c408          add esp,+08
> [00001365](02)  85c0            test eax,eax
> [00001367](02)  7402            jz 0000136b
> [00001369](02)  ebfe            jmp 00001369
> [0000136b](01)  5d              pop ebp
> [0000136c](01)  c3              ret
> Size in bytes:(0027) [0000136c]
> 
> It is completely obvious that when H(P,P) correctly emulates its
> input that it must emulate the first seven instructions of P.
> 
> Because the seventh instruction repeats this process we can know with 
> complete certainty that the emulated P never reaches its final “ret” 
> instruction, thus never halts.
> 
> 
> 
> Halting problem undecidability and infinitely nested simulation (V5)
> 
> https://www.researchgate.net/publication/359984584_Halting_problem_undecidability_and_infinitely_nested_simulation_V5 

Unfortunately your logic is such that the decision as to whether or not
to enter the infinite loop is predicated on an infinite recursion (call
H) that is not present in the Halting Problem proofs you are attempting
to refute.

/Flibble

Back to comp.software-eng | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Re: Refuting the HP proofs (adapted for software engineers) Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-06-04 00:35 +0100
  Re: Refuting the HP proofs (adapted for software engineers)[ Andy Walker ] olcott <NoOne@NoWhere.com> - 2022-06-03 18:56 -0500

csiph-web