Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| Subject | Re: How is H(P,P)==0 correct even though P(P) stops running? |
|---|---|
| Newsgroups | comp.theory |
| References | <prednSOZ5uphDmT9nZ2dnUU7-bvNnZ2d@giganews.com> <VJidnWCiJf8RBGT9nZ2dnUU7-d-dnZ2d@giganews.com> |
| From | Richard Damon <Richard@Damon-Family.org> |
| Message-ID | <b2iKI.22498$uj5.8074@fx03.iad> (permalink) |
| Organization | Forte - www.forteinc.com |
| Date | 2021-07-22 10:38 -0700 |
On 7/22/21 9:15 AM, olcott wrote:
> On 7/22/2021 10:51 AM, olcott wrote:
>> How is H(P,P)==0 correct even though P(P) stops running?
>>
>> (a) The reason that P of int main(){ P(P); } it is construed as
>> halting is that it reaches its final state.
>>
>> (b) The reason that it reaches its final state is that H(P,P) returns
>> zero.
>>
>> (c) The reason that H(P,P) returns zero is that the correct pure
>> simulation of its input can't possibly reach its final state.
>>
>
> We can easily verify that the pure simulation of the input to
> H(P,P) is correct when we verify that the execution trace of
> the simulation of P(P) precisely corresponds to the x86
> source-code of P.
>
You mean the trace that makes the logical error of replacing the trace
of a simulation that isn't unconditional with the trace of the simulation.
That operation is ONLY valid if the simulator NEVER stops its simulation.
UNSOUND LOGIC.
> We can easily verify that the pure simulation of the input to
> H(P,P) never reaches the final state of P by examining the
> execution trace of the simulation of P(P) under the assumption
> that the call to H at machine address 0x955 is a call to a pure
> x86 emulator.
Right, if you make a FALSE assumption, then you get an UNSOUND results.
If you assume that H is a pure simulator, but it isn't, then you are
using unsound logic.
>
> We can know that this assumption is valid because we know that H
> is computationally equivalent to a pure simulator of its input
> until after it makes its halt status decision.
But then it isn't. Computation are complete units, from start to end,
the fact that it works one way for a while and then an other doesn't
mean you can just assume that it is the first class.
H is NOT a 'pure simulator' so you can't treat it as one.
It you wanted to try oto use that logic, H would have to simulate the H
that it is simulating until THAT simulated H reached its decision, which
you don't.
>
>
>> (d) When the pure simulation of an input can't possibly ever reach its
>> final state then this input never halts.
But you have posted a trace of the 'pure simulation' of P(P) showing
that it does come to a halt after the H that it calls aborts its
simulation and returns the non-halting answer.
Note, your arguement MEANS running a simulation of P(P), NOT as you make
in your argument changing H to be a pure simulation, which changes P and
gives you an H that never returns an answer for H(P,P)
>>
>> ∴ The only reason that P of int main(){ P(P); } halts is because
>> H(P,P) correctly decided that its input never halts.
>>
>> We can easily verify that the simulation of P(P) is correct by
>> comparing the execution trace of this simulation to the x86
>> source-code of P shown below.
>>
>> (c) is proved in that when P calls H and H acts as a pure simulator of
>> P(P) it is very obvious that P(P) is stuck in infinitely nested
>> simulation when we examine the execution trace of the simulation of
>> P(P) shown below:
>>
>> // Strachey(1965) "An impossible program"
>> // CPL translated to C
>> // https://doi.org/10.1093/comjnl/7.4.313
>> void P(u32 x)
>> {
>> if (H(x, x))
>> HERE: goto HERE;
>> }
>>
>> int main()
>> {
>> P((u32)P);
>> }
>>
>> _P()
>> [00000c25](01) 55 push ebp
>> [00000c26](02) 8bec mov ebp,esp
>> [00000c28](03) 8b4508 mov eax,[ebp+08]
>> [00000c2b](01) 50 push eax // 2nd Param
>> [00000c2c](03) 8b4d08 mov ecx,[ebp+08]
>> [00000c2f](01) 51 push ecx // 1st Param
>> [00000c30](05) e820fdffff call 00000955 // call H
>> [00000c35](03) 83c408 add esp,+08
>> [00000c38](02) 85c0 test eax,eax
>> [00000c3a](02) 7402 jz 00000c3e
>> [00000c3c](02) ebfe jmp 00000c3c
>> [00000c3e](01) 5d pop ebp
>> [00000c3f](01) c3 ret
>> Size in bytes:(0027) [00000c3f]
>>
>> _main()
>> [00000c45](01) 55 push ebp
>> [00000c46](02) 8bec mov ebp,esp
>> [00000c48](05) 68250c0000 push 00000c25 // push P
>> [00000c4d](05) e8d3ffffff call 00000c25 // call P
>> [00000c52](03) 83c404 add esp,+04
>> [00000c55](02) 33c0 xor eax,eax
>> [00000c57](01) 5d pop ebp
>> [00000c58](01) c3 ret
>> Size in bytes:(0020) [00000c58]
>>
>> machine stack stack machine assembly
>> address address data code language
>> ======== ======== ======== ========= =============
>> [00000c45][001016d6][00000000] 55 push ebp
>> [00000c46][001016d6][00000000] 8bec mov ebp,esp
>> [00000c48][001016d2][00000c25] 68250c0000 push 00000c25 // push P
>> [00000c4d][001016ce][00000c52] e8d3ffffff call 00000c25 // call P0
>> [00000c25][001016ca][001016d6] 55 push ebp // P0 begins
>> [00000c26][001016ca][001016d6] 8bec mov ebp,esp
>> [00000c28][001016ca][001016d6] 8b4508 mov eax,[ebp+08]
>> [00000c2b][001016c6][00000c25] 50 push eax // push P
>> [00000c2c][001016c6][00000c25] 8b4d08 mov ecx,[ebp+08]
>> [00000c2f][001016c2][00000c25] 51 push ecx // push P
>> [00000c30][001016be][00000c35] e820fdffff call 00000955 // call H0
>>
>> Begin Local Halt Decider Simulation at Machine Address:c25
>> [00000c25][00211776][0021177a] 55 push ebp // P1 begins
>> [00000c26][00211776][0021177a] 8bec mov ebp,esp
>> [00000c28][00211776][0021177a] 8b4508 mov eax,[ebp+08]
>> [00000c2b][00211772][00000c25] 50 push eax // push P
>> [00000c2c][00211772][00000c25] 8b4d08 mov ecx,[ebp+08]
>> [00000c2f][0021176e][00000c25] 51 push ecx // push P
>> [00000c30][0021176a][00000c35] e820fdffff call 00000955 // call H1
>> [00000c25][0025c19e][0025c1a2] 55 push ebp // P2 begins
>> [00000c26][0025c19e][0025c1a2] 8bec mov ebp,esp
>> [00000c28][0025c19e][0025c1a2] 8b4508 mov eax,[ebp+08]
>> [00000c2b][0025c19a][00000c25] 50 push eax // push P
>> [00000c2c][0025c19a][00000c25] 8b4d08 mov ecx,[ebp+08]
>> [00000c2f][0025c196][00000c25] 51 push ecx // push P
>> [00000c30][0025c192][00000c35] e820fdffff call 00000955 // call H2
>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>>
>> In the above computation (zero based addressing) H0 aborts P1.
>>
>> [00000c35][001016ca][001016d6] 83c408 add esp,+08
>> [00000c38][001016ca][001016d6] 85c0 test eax,eax
>> [00000c3a][001016ca][001016d6] 7402 jz 00000c3e
>> [00000c3e][001016ce][00000c52] 5d pop ebp
>> [00000c3f][001016d2][00000c25] c3 ret
>> [00000c52][001016d6][00000000] 83c404 add esp,+04
>> [00000c55][001016d6][00000000] 33c0 xor eax,eax
>> [00000c57][001016da][00100000] 5d pop ebp
>> [00000c58][001016de][00000084] c3 ret
>> Number_of_User_Instructions(34)
>> Number of Instructions Executed(23729)
>>
>> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>>
>>
>
>
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-22 10:51 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-22 11:15 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-22 10:38 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-22 10:34 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-22 13:16 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-22 11:39 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-24 00:11 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 23:14 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-22 19:30 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-22 14:17 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-22 12:42 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-23 00:04 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-22 18:25 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-23 00:48 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 08:53 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 08:50 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 11:00 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 09:31 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 12:13 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 11:31 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 13:42 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 11:56 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 14:07 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 12:23 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 15:38 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 13:53 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 15:56 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 14:25 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? André G. Isaak <agisaak@gm.invalid> - 2021-07-23 17:49 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-24 03:56 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? Andy Walker <anw@cuboid.co.uk> - 2021-07-24 12:40 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-07-24 04:52 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-24 08:55 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Andy Walker <anw@cuboid.co.uk> - 2021-07-24 16:44 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-24 10:54 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-24 09:08 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-24 08:50 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-24 09:16 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? André G. Isaak <agisaak@gm.invalid> - 2021-07-24 10:31 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? [ pure simulator ] olcott <NoOne@NoWhere.com> - 2021-07-24 09:34 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ pure simulator ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 09:25 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? André G. Isaak <agisaak@gm.invalid> - 2021-07-23 17:42 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 19:26 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? André G. Isaak <agisaak@gm.invalid> - 2021-07-23 19:02 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 20:32 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 18:42 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 20:50 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 19:28 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 23:38 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 23:17 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar? ] olcott <NoOne@NoWhere.com> - 2021-07-24 09:05 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 09:31 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] olcott <NoOne@NoWhere.com> - 2021-07-24 12:23 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 11:34 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] olcott <NoOne@NoWhere.com> - 2021-07-24 13:42 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] André G. Isaak <agisaak@gm.invalid> - 2021-07-24 13:07 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] olcott <NoOne@NoWhere.com> - 2021-07-24 14:22 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 12:38 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] olcott <NoOne@NoWhere.com> - 2021-07-24 15:01 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 13:14 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-25 04:07 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-25 21:02 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-25 21:33 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? [ Internals of H ] olcott <NoOne@NoWhere.com> - 2021-07-26 10:08 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 12:21 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] olcott <NoOne@NoWhere.com> - 2021-07-24 14:24 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 12:44 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] olcott <NoOne@NoWhere.com> - 2021-07-24 15:03 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 13:19 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] André G. Isaak <agisaak@gm.invalid> - 2021-07-24 16:10 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] olcott <NoOne@NoWhere.com> - 2021-07-24 17:31 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [ liar ??? ] André G. Isaak <agisaak@gm.invalid> - 2021-07-24 16:46 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? André G. Isaak <agisaak@gm.invalid> - 2021-07-23 19:44 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? [focused until mutual agreement ] olcott <NoOne@NoWhere.com> - 2021-07-24 09:23 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [focused until mutual agreement ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 09:33 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? [focused until mutual agreement ] olcott <NoOne@NoWhere.com> - 2021-07-24 12:41 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? [focused until mutual agreement ] Richard Damon <Richard@Damon-Family.org> - 2021-07-24 11:39 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 18:00 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-23 22:12 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 16:49 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 15:26 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-25 04:07 +0100
Re: How is H(P,P)==0 correct even though P(P) stops running? André G. Isaak <agisaak@gm.invalid> - 2021-07-22 13:11 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-22 17:18 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-22 15:46 -0700
Re: How is H(P,P)==0 correct even though P(P) stops running? André G. Isaak <agisaak@gm.invalid> - 2021-07-22 17:08 -0600
Re: How is H(P,P)==0 correct even though P(P) stops running? olcott <NoOne@NoWhere.com> - 2021-07-23 09:35 -0500
Re: How is H(P,P)==0 correct even though P(P) stops running? Richard Damon <Richard@Damon-Family.org> - 2021-07-23 09:48 -0700
csiph-web