Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #3488 > unrolled thread
| Started by | Mr Flibble <flibble@reddwarf.jmc.corp> |
|---|---|
| First post | 2022-06-04 00:35 +0100 |
| Last post | 2022-06-03 18:56 -0500 |
| Articles | 2 — 2 participants |
Back to article view | Back to comp.software-eng
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
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
| From | Mr Flibble <flibble@reddwarf.jmc.corp> |
|---|---|
| Date | 2022-06-04 00:35 +0100 |
| Subject | Re: Refuting the HP proofs (adapted for software engineers) |
| Message-ID | <20220604003502.00007f80@reddwarf.jmc.corp> |
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
[toc] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2022-06-03 18:56 -0500 |
| Subject | Re: Refuting the HP proofs (adapted for software engineers)[ Andy Walker ] |
| Message-ID | <wsOdnSKt5-09Agf_nZ2dnUU7_8zNnZ2d@giganews.com> |
| In reply to | #3488 |
On 6/3/2022 6:35 PM, Mr Flibble wrote:
> 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
>
It is when a simulating halt decider is assumed.
No one ever bothered to think the otherwise "impossible" input being
analyzed by a simulating halt decider ALL THE WAY THROUGH EVER BEFORE!
On 6/2/2022 1:12 PM, Andy Walker wrote:
> http://www.cuboid.me.uk/anw/G12FCO/lect18.html
At any given moment as the emulation proceeds, we are in one of not two
but three states: the program has halted, or it is looping, or it is
still running and has not yet entered a loop. It's the third case that
kills us -- we just have to keep going, and wait for one of the other
two things to happen. The trouble is that it may be that neither of them
ever happens -- which is why `it must be in a loop' was in quotes above.
Andy Walker did provide a fundamentally flawed and totally shallow
analysis of an simulating halt decider.
At any given moment as the emulation proceeds,
we are in one of not two but three states:
(a) The program has halted,
(b) It is still running.
(c) IT HAS MATCHED AN INFINITE BEHAVIOR PATTERN
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
return;
}
The above matches (c) for infinitely nested simulation.
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
[toc] | [prev] | [standalone]
Back to top | Article view | comp.software-eng
csiph-web