Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #36507 > unrolled thread
| Started by | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| First post | 2021-07-17 13:50 +0100 |
| Last post | 2021-07-17 07:36 -0700 |
| Articles | 11 on this page of 111 — 9 participants |
Back to article view | Back to comp.theory
Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 13:50 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 13:22 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 14:37 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 13:59 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 15:06 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 09:17 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 14:20 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 15:24 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 14:34 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 15:38 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 14:45 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 15:53 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 15:12 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) [ Rice's Theorem ] olcott <NoOne@NoWhere.com> - 2021-07-17 11:53 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 20:38 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 wij <wyniijj@gmail.com> - 2021-07-17 08:04 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 16:12 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 wij <wyniijj@gmail.com> - 2021-07-17 08:25 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 16:28 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 wij <wyniijj@gmail.com> - 2021-07-17 08:37 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 11:58 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-17 14:17 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 11:23 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 17:45 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 12:08 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 11:17 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 20:05 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 15:19 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-17 20:51 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 16:48 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-18 10:57 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Richard Damon <Richard@Damon-Family.org> - 2021-07-18 07:36 -0600
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-19 08:58 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Richard Damon <Richard@Damon-Family.org> - 2021-07-19 08:23 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-19 18:20 +0000
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-20 08:25 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Alan Mackenzie <acm@muc.de> - 2021-07-20 17:35 +0000
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 13:26 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Alan Mackenzie <acm@muc.de> - 2021-07-20 18:53 +0000
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 14:04 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 12:27 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 13:49 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 17:14 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 16:27 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 18:20 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 18:34 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 21:04 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 20:24 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 22:06 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 20:21 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 21:26 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 22:53 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 22:02 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) olcott <NoOne@NoWhere.com> - 2021-07-20 23:24 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 22:12 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) André G. Isaak <agisaak@gm.invalid> - 2021-07-20 23:32 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ DOES NOT HOLD ] olcott <NoOne@NoWhere.com> - 2021-07-21 09:11 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ DOES NOT HOLD ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 10:03 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ DOES NOT HOLD ] olcott <NoOne@NoWhere.com> - 2021-07-21 11:11 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ DOES NOT HOLD ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 10:42 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ DOES NOT HOLD ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 10:16 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 21:23 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 11:45 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 10:22 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-21 12:23 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 10:41 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 12:26 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-21 13:54 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 13:26 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-21 14:44 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 12:56 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 15:09 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] olcott <NoOne@NoWhere.com> - 2021-07-21 16:29 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 15:02 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-07-21 21:08 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ global halt decider ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 12:55 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 11:29 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 12:51 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 12:19 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 13:49 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 13:22 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 14:43 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 13:12 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ][ADD] olcott <NoOne@NoWhere.com> - 2021-07-21 16:07 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ][ADD] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 14:32 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ][ADD] olcott <NoOne@NoWhere.com> - 2021-07-21 16:50 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ][ADD] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 15:07 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 15:06 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 16:22 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 14:38 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 15:57 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 17:21 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 15:53 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] André G. Isaak <agisaak@gm.invalid> - 2021-07-21 16:59 -0600
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 20:21 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 18:53 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 13:07 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] olcott <NoOne@NoWhere.com> - 2021-07-21 15:29 -0500
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) [ Paradox rather than contradiction ] Richard Damon <Richard@Damon-Family.org> - 2021-07-21 14:08 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 19:33 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 18:07 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 12:14 -0700
Re: Halting Problem Solved? ( H(P,P)==0 is correct ) Richard Damon <Richard@Damon-Family.org> - 2021-07-20 12:06 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Richard Damon <Richard@Damon-Family.org> - 2021-07-20 10:39 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Andy Walker <anw@cuboid.co.uk> - 2021-07-17 15:55 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 09:18 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 15:20 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 olcott <NoOne@NoWhere.com> - 2021-07-17 11:13 -0500
Re: Halting Problem Solved? (Black Box Decider Theory) V2 wij <wyniijj@gmail.com> - 2021-07-17 06:57 -0700
Re: Halting Problem Solved? (Black Box Decider Theory) V2 Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 15:17 +0100
Re: Halting Problem Solved? (Black Box Decider Theory) V2 wij <wyniijj@gmail.com> - 2021-07-17 07:36 -0700
Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-07-20 18:07 -0700 |
| Subject | Re: Halting Problem Solved? ( H(P,P)==0 is correct ) |
| Message-ID | <drKJI.25012$ilwe.7498@fx35.iad> |
| In reply to | #36735 |
On 7/20/21 3:14 PM, olcott wrote: > On 7/20/2021 2:49 PM, André G. Isaak wrote: >> On 2021-07-20 13:04, olcott wrote: >>> On 7/20/2021 1:53 PM, Alan Mackenzie wrote: >>>> [ Malicious cross posting removed ] >>>> >>>> In comp.theory olcott <NoOne@nowhere.com> wrote: >>>>> On 7/20/2021 12:35 PM, Alan Mackenzie wrote: >>>>>> [ Malicious cross posting removed ] >>>> >>>>>> In comp.theory olcott <NoOne@nowhere.com> wrote: >>>> >>>> [ .... ] >>>> >>>>>>> I show all the steps of exactly how H(P,P)==0 is derived. >>>> >>>>>> You don't. You haven't yet published the source code of an >>>>>> alleged H. >>>> >>>>>>> That you simply ignore these steps and claim that I am incorrect is >>>>>>> simply dishonest. >>>> >>>>>> No, it's being dishonest to indulge you with the suggestion that what >>>>>> you are doing has any possible validity. It is unimportant and >>>>>> uninteresting why H(P,P)==0, if it actually is. It has no bearing on >>>>>> the halting theorem proofs, which work regardless of the nature of >>>>>> any >>>>>> purported halting decider. Seeing as how you can't disprove these >>>>>> proofs honestly, you resort to falsehoods and obfuscation. Even so, >>>>>> the other posters on this newsgroup have seen through it and exposed >>>>>> it. When is all this nonsense going to end? >>>> >>>> [ .... ] >>>> >>>>> All of the proofs conclusively prove that H cannot possibly return a >>>>> Boolean value corresponding to the actual halt status of P to P in the >>>>> above computation. >>>> >>>> Wow! >>>> >>>>> None of the proofs bother to examine whether or not returning a >>>>> correct >>>>> halt status from H to P in the above computation is required, they >>>>> simply assume that it is required. *That is their error* >>>> >>>> For crying out loud! It is an error to require what is required by the >>>> statement of the problem? The central element of the halting >>>> problem is >>>> a *UNIVERSAL* halting decider. And you're saying insisting upon this >>>> *universality* is an error? >>>> >>> >>> I universal halt decider is one thing. >>> >>> A universal halt decider that must return a correct halt status to an >>> input that does the opposite of whatever it decides is a much >>> narrower specification. >> >> 'Universal' means it decides all Turing Machines. The latter would >> case would be included in 'universal'. so if it cannot return the >> correct decision in that case it is not universal. >> > > It is not strictly necessary for a halt decider to return any value to > its input. This is merely a false assumption. H in main() aborts the > simulation of P before the simulation of H in P ever returns any value > to P. All of P including the simulation of H in P is strictly controlled > by the H in main(): NO program returns a value to its 'Input'. The decider must return a value to its caller. The Halting Question is does P(I) Halt when it is run, so we need to look at the execution of H^(H^) to see if H(H^,H^) is right, and that H^(H^) is NOT aborted by any H (as it isn't run under any H) and that H^ will come to a Halt, and thus is a Halting Computation. Note, this means the computation that we really want to look at is the one where main calls our H^ (which you are now calling P) and that calls H. In that case, H MUST return its answer to that calling P, and it returns the non-halting answer, and then P halts, showing H to be wrong.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-07-20 12:14 -0700 |
| Subject | Re: Halting Problem Solved? ( H(P,P)==0 is correct ) |
| Message-ID | <ZfFJI.38442$UR4.5024@fx37.iad> |
| In reply to | #36718 |
On 7/20/21 11:53 AM, Alan Mackenzie wrote: > [ Malicious cross posting removed ] > > In comp.theory olcott <NoOne@nowhere.com> wrote: >> On 7/20/2021 12:35 PM, Alan Mackenzie wrote: >>> [ Malicious cross posting removed ] > >>> In comp.theory olcott <NoOne@nowhere.com> wrote: > > [ .... ] > >>>> I show all the steps of exactly how H(P,P)==0 is derived. > >>> You don't. You haven't yet published the source code of an alleged H. > >>>> That you simply ignore these steps and claim that I am incorrect is >>>> simply dishonest. > >>> No, it's being dishonest to indulge you with the suggestion that what >>> you are doing has any possible validity. It is unimportant and >>> uninteresting why H(P,P)==0, if it actually is. It has no bearing on >>> the halting theorem proofs, which work regardless of the nature of any >>> purported halting decider. Seeing as how you can't disprove these >>> proofs honestly, you resort to falsehoods and obfuscation. Even so, >>> the other posters on this newsgroup have seen through it and exposed >>> it. When is all this nonsense going to end? > > [ .... ] > >> All of the proofs conclusively prove that H cannot possibly return a >> Boolean value corresponding to the actual halt status of P to P in the >> above computation. > > Wow! > >> None of the proofs bother to examine whether or not returning a correct >> halt status from H to P in the above computation is required, they >> simply assume that it is required. *That is their error* > > For crying out loud! It is an error to require what is required by the > statement of the problem? The central element of the halting problem is > a *UNIVERSAL* halting decider. And you're saying insisting upon this > *universality* is an error? > > Don't be stupid. There is no error in these proofs. No, he is right that when we run H(H^,H^) that this H isn't 'required' to run its simulation far enough to see that H^(H^) call H*H^,H^) and then see that simulated H return an answer. Of course, not getting enough information makes it hard to predict what the behavior will be. What he keeps on doing is ignore that it aborting the simulation doens't change the behavior of the machine being simulated, which when we run H^(H^) as an actual machine shows that H^(H^) will call H*H^,H^) which will return the non-halting answer, and then H^ halts, showing that the simulation, if allowed to run, would have done the same thing, and thus the 'Proof' that H^(H^) will never halt must be flawed. > >> The paper shows the actual execution trace of the simulation of P(P) by >> H cannot possibly ever stop running unless its simulation is aborted. > > That's part of the internal design of the alleged H, and has no relevance > for the proofs we're talking about > >> Because this is the definition of a computation that never halts >> H(P,P)==0 is impossibly incorrect. > > "Impossibly correct" is meaningless. The point here is that if H is a > non-halting computation, it is not a halting decider, regardless of > anything else. > >> -- >> Copyright 2021 Pete Olcott > >> "Great spirits have always encountered violent opposition from mediocre >> minds." Einstein >
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-07-20 12:06 -0700 |
| Subject | Re: Halting Problem Solved? ( H(P,P)==0 is correct ) |
| Message-ID | <69FJI.50438$dp5.5547@fx48.iad> |
| In reply to | #36716 |
On 7/20/21 11:26 AM, olcott wrote:
> On 7/20/2021 12:35 PM, Alan Mackenzie wrote:
>> [ Malicious cross posting removed ]
>>
>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>> On 7/19/2021 1:20 PM, Alan Mackenzie wrote:
>>>> [ Malicious cross posting removed ]
>>
>>>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>
>> [ .... ]
>>
>>>>> Ignoring that I proved that H(P,P)==0 is correct is not a rebuttal.
>>
>>>> No, it's an insistence on the validity of a proven theorem.
>>>> *You*'re the
>>>> one attempting rebuttal. Like I've said before, the proofs of the
>>>> halting problem theorem are independent of the internal workings of
>>>> purported halt deciders, so those internal workings just aren't
>>>> interesting. H doesn't exist.
>>
>>> I show all the steps of exactly how H(P,P)==0 is derived.
>>
>> You don't. You haven't yet published the source code of an alleged H.
>>
>>> That you simply ignore these steps and claim that I am incorrect is
>>> simply dishonest.
>>
>> No, it's being dishonest to indulge you with the suggestion that what you
>> are doing has any possible validity. It is unimportant and uninteresting
>> why H(P,P)==0, if it actually is. It has no bearing on the halting
>> theorem proofs, which work regardless of the nature of any purported
>> halting decider. Seeing as how you can't disprove these proofs honestly,
>> you resort to falsehoods and obfuscation. Even so, the other posters on
>> this newsgroup have seen through it and exposed it. When is all this
>> nonsense going to end?
>>
>
> // 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()
> {
> Output("Input_Halts = ", H((u32)P, (u32)P));
> }
>
> All of the proofs conclusively prove that H cannot possibly return a
> Boolean value corresponding to the actual halt status of P to P in the
> above computation.
>
> None of the proofs bother to examine whether or not returning a correct
> halt status from H to P in the above computation is required, they
> simply assume that it is required. *That is their error*
>
Well, that is basically the DEFINITION of a correct decider. A Correct
Decider is a Machine that return the right answer for the question it is
given.
A Turing Machine preforms a computation, so it ALWAYS returns the same
answer to ALL callers for a given set of inputs.
Thus, when main calls P (which should be H_Hat) then H needs to return
to THAT P the same answer, and then that P will halt, thus showing BY
DEFINITION that P(P) is a Halting Computation.
Yes, in your case above, H doesn't NEED to simulate P far enough for the
H that it calls to return its answer to the simulated P, but if it
doesn't then it seems hard to understand how it can possibly get the
right answer except by chance.
The key is that, as I said, the ACTUAL computation that we need to
examine to know what the right answer is when main directly calls P(P),
and in THAT computation, the H that this P calls DOES need to return its
answer to it, or H fails to meet the requirements of being a decider.
> The paper shows the actual execution trace of the simulation of P(P) by
> H cannot possibly ever stop running unless its simulation is aborted.
> Because this is the definition of a computation that never halts
> H(P,P)==0 is impossibly incorrect.
Which has many times been pointed out to be in error.
>
> https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
>
>
>> [ .... ]
>>
>>> --
>>> Copyright 2021 Pete Olcott
>>
>>> "Great spirits have always encountered violent opposition from mediocre
>>> minds." Einstein
>>
>
>
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-07-20 10:39 -0700 |
| Message-ID | <jTDJI.5267$gE.2540@fx21.iad> |
| In reply to | #36695 |
On 7/20/21 6:25 AM, olcott wrote:
> On 7/19/2021 1:20 PM, Alan Mackenzie wrote:
>> [ Malicious cross posting removed ]
>>
>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>> On 7/18/2021 5:57 AM, Alan Mackenzie wrote:
>>>> [ Malicious cross posting removed ]
>>
>>>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>>>> On 7/17/2021 3:51 PM, Alan Mackenzie wrote:
>>>>>> [ Malicious cross posting snipped. ]
>>
>>>>>> In comp.theory olcott <NoOne@nowhere.com> wrote:
>>>>>>> On 7/17/2021 3:05 PM, Alan Mackenzie wrote:
>>>>>>>> [ Malicious cross posting removed ]
>>
>>>> [ .... ]
>>
>>>>>>>> Brainwashed to have a correct overview which Olcott lacks? How
>>>>>>>> about you actually read what I wrote before answering at
>>>>>>>> half-cock? My point was that these programs, though they may have
>>>>>>>> a special relationship with a purported halt decider, are
>>>>>>>> otherwise perfectly ordinary programs which run, and either halt
>>>>>>>> or fail to halt. The purported halt decider will give the wrong
>>>>>>>> answer for such programs.
>>
>>>>>>> You have proven much more honest than Ben on this he never ever
>>>>>>> acknowledged any *special relationship*
>>
>>>>>>> The key is that *special relationship* is what has made them unable
>>>>>>> to provide the correct halt status, thus making the *special
>>>>>>> relationship* harmful AKA pathological.
>>
>>>>>> What do you mean, harmful? There's nothing here which will kill
>>>>>> polar bears, increase the amount of carbon dioxide in the atmosphere
>>>>>> or cause floods or droughts. There's nothing pathalogical here,
>>>>>> either - these
>>
>>>>> The fact that the *special relationship* (without my solution) ....
>>
>>>> With or without your "solution", which isn't one.
>>
>>> Ignoring that I proved that H(P,P)==0 is correct is not a rebuttal.
>>
>> No, it's an insistence on the validity of a proven theorem. *You*'re the
>> one attempting rebuttal. Like I've said before, the proofs of the
>> halting problem theorem are independent of the internal workings of
>> purported halt deciders, so those internal workings just aren't
>> interesting. H doesn't exist.
>>
>
> I show all the steps of exactly how H(P,P)==0 is derived. That you
> simply ignore these steps and claim that I am incorrect is simply
> dishonest.
>
> Simulating partial halt decider H correctly decides that P(P) never
> halts (V0)
>
> // 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()
> {
> Output("Input_Halts = ", H((u32)P, (u32)P));
> }
>
> _P()
> [00000c36](01) 55 push ebp
> [00000c37](02) 8bec mov ebp,esp
> [00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
> [00000c3c](01) 50 push eax
> [00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
> [00000c40](01) 51 push ecx
> [00000c41](05) e820fdffff call 00000966 // call H
> [00000c46](03) 83c408 add esp,+08
> [00000c49](02) 85c0 test eax,eax
> [00000c4b](02) 7402 jz 00000c4f
> [00000c4d](02) ebfe jmp 00000c4d
> [00000c4f](01) 5d pop ebp
> [00000c50](01) c3 ret
> Size in bytes:(0027) [00000c50]
>
> _main()
> [00000c56](01) 55 push ebp
> [00000c57](02) 8bec mov ebp,esp
> [00000c59](05) 68360c0000 push 00000c36
> [00000c5e](05) 68360c0000 push 00000c36
> [00000c63](05) e8fefcffff call 00000966
> [00000c68](03) 83c408 add esp,+08
> [00000c6b](01) 50 push eax
> [00000c6c](05) 6857030000 push 00000357
> [00000c71](05) e810f7ffff call 00000386
> [00000c76](03) 83c408 add esp,+08
> [00000c79](02) 33c0 xor eax,eax
> [00000c7b](01) 5d pop ebp
> [00000c7c](01) c3 ret
> Size in bytes:(0039) [00000c7c]
>
> machine stack stack machine assembly
> address address data code language
> ======== ======== ======== ========= =============
> [00000c56][0010172a][00000000] 55 push ebp
> [00000c57][0010172a][00000000] 8bec mov ebp,esp
> [00000c59][00101726][00000c36] 68360c0000 push 00000c36
> [00000c5e][00101722][00000c36] 68360c0000 push 00000c36
> [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)
>
> Begin Local Halt Decider Simulation at Machine Address:c36
> [00000c36][002117ca][002117ce] 55 push ebp
> [00000c37][002117ca][002117ce] 8bec mov ebp,esp
> [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
> [00000c3c][002117c6][00000c36] 50 push eax
> [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
> [00000c40][002117c2][00000c36] 51 push ecx
> [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)
So, why doesn't the trace show the trace of H at 966?
The code of H here is PART of the algorithm of P, so its actions are
PART of what the decider H needs to take into account. The fact that H
will eventually abort its simulation of its input P means that just
showing the trace of P isn't an accurate trace of execution of the
machine P that called this H.
> [00000c36][0025c1f2][0025c1f6] 55 push ebp
> [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
> [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
> [00000c3c][0025c1ee][00000c36] 50 push eax
> [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
> [00000c40][0025c1ea][00000c36] 51 push ecx
> [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>
> [00000c68][0010172a][00000000] 83c408 add esp,+08
> [00000c6b][00101726][00000000] 50 push eax
> [00000c6c][00101722][00000357] 6857030000 push 00000357
> [00000c71][00101722][00000357] e810f7ffff call 00000386
> Input_Halts = 0
> [00000c76][0010172a][00000000] 83c408 add esp,+08
> [00000c79][0010172a][00000000] 33c0 xor eax,eax
> [00000c7b][0010172e][00100000] 5d pop ebp
> [00000c7c][00101732][00000068] c3 ret
> Number_of_User_Instructions(27)
> Number of Instructions Executed(23721)
>
>
[toc] | [prev] | [next] | [standalone]
| From | Andy Walker <anw@cuboid.co.uk> |
|---|---|
| Date | 2021-07-17 15:55 +0100 |
| Message-ID | <scur0v$qi5$1@gioia.aioe.org> |
| In reply to | #36515 |
On 17/07/2021 15:06, Mr Flibble wrote:
[...]
>>> .... which are uninteresting cases because presumably we are using a
>>> decider to decide legitimate programs that have serve some useful
>>> purpose beyond the HP itself.
Yes, and no. As with NP-completeness, most of the point is not
the /actual/ halt status [or complexity status] but the practical time
saved by knowing that something is impossible [or very difficult]. If
someone asks you to write a program that determines whether some other
program ever reaches line 37, we already know that to be impossible
/in general/ as it reducible to the HP. There may still be partial
solutions that are good enough [for "some useful purpose", as you put
it]. That is, for example, why "good" [FSVO] algorithms come with
proofs of correctness and termination; the proofs can themselves be
mechanically checked for correctness, which at least kicks the can
down the road and past the first bend.
[AlanM:]
>> Then you're not talking about the standard halting problem. That
>> shows the impossibility of a decider which can decide ANY program.
>> If you limit the scope of the programs handled, then you might well
>> construct a practically useful partial decider. Difficult, but
>> possible. There are probably theorems about the sort of things that
>> are possible here, but I don't know them.
Wiki has quite a lot in this area. But, for example, one of
the undecidable things is whether or not a given program is a partial
halt decider [ie, correctly replies "Yes", "No" or "Don't know"]. Of
course, some PHDs exist and can be proven to be PHDs; as usual, it's
the general problem that is of theoretical interest.
OTOH, the only tool I know of to generate more than trivial
PHDs is emulation; and as soon as you use that, then in practical
terms you are lost. Inevitably, the emulation is slower than the
real thing*, so to find out whether something completes within, say,
10 years, you may have to run the emulation for, say, 30 years, and
you might as well run the original [in a sandbox, if necessary].
>> None of this has any relevance for the theoremhood of the halting
>> problem result itself.
> Disagree: having a third result for invalid pathological programs
> whilst novel is still a result, i.e. a decision reached in finite time.
It's not "novel" [tho' some of your mechanisms may be]; see
the Wiki article on the HP. But detecting "pathological" cases is as
hard as the HP, so you haven't really gained anything. As above, there
are any number of useful "Yes"/"No"/"Don't_know" PHDs already out
there. As Alan says, they are not relevant to whether or not the HP
result is a correct theorem. If you don't like the Strachey-type
proofs, then the proof via "Busy Beaver" is elementary, and does
not rely on anything remotely pathological. The HP is not usually
discussed via BB simply because it can be discussed entirely in its
own terms, which is more self-contained pedagogically.
____
* Not quite inevitable. For example, we could imagine slow but
cheap hardware being tested by emulation on fast but expensive
computers before mass installation in washing machines, cars,
doorknobs or whatever. But not the point in relation to HP.
--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Mayer
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-17 09:18 -0500 |
| Message-ID | <R56dnVdOjoBVe2_9nZ2dnUU7-X-dnZ2d@giganews.com> |
| In reply to | #36510 |
On 7/17/2021 8:37 AM, Mr Flibble wrote: > On Sat, 17 Jul 2021 13:22:56 -0000 (UTC) > Alan Mackenzie <acm@muc.de> wrote: >> Not really - you don't have a universal halting decider here by >> design. And even if you did, the signature wouldn't do anything to >> prevent the existence of the programs which have an "invalid >> relationship" with D. > > The point is that this "invalid relationship" is DETECTABLE by the > black box decider. This "invalid relationship" only exists for programs > which are deliberately designed to defeat the decider which are > uninteresting cases because presumably we are using a decider to decide > legitimate programs that have serve some useful purpose beyond the HP itself. > > /Flibble > We might as well have a black box cure for cancer or a black box cure for violence in the world. Unless you say how it works it don't count. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 15:20 +0100 |
| Message-ID | <20210717152020.00001ff7@reddwarf.jmc> |
| In reply to | #36518 |
On Sat, 17 Jul 2021 09:18:50 -0500 olcott <NoOne@NoWhere.com> wrote: > On 7/17/2021 8:37 AM, Mr Flibble wrote: > > On Sat, 17 Jul 2021 13:22:56 -0000 (UTC) > > Alan Mackenzie <acm@muc.de> wrote: > >> Not really - you don't have a universal halting decider here by > >> design. And even if you did, the signature wouldn't do anything to > >> prevent the existence of the programs which have an "invalid > >> relationship" with D. > > > > The point is that this "invalid relationship" is DETECTABLE by the > > black box decider. This "invalid relationship" only exists for > > programs which are deliberately designed to defeat the decider > > which are uninteresting cases because presumably we are using a > > decider to decide legitimate programs that have serve some useful > > purpose beyond the HP itself. > > > > /Flibble > > > > We might as well have a black box cure for cancer or a black box cure > for violence in the world. Unless you say how it works it don't count. You haven't shown how your x86 omnishambles works so it "don't count". /Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-17 11:13 -0500 |
| Message-ID | <2a6dnWhEj6oMnG79nZ2dnUU7-fvNnZ2d@giganews.com> |
| In reply to | #36519 |
On 7/17/2021 9:20 AM, Mr Flibble wrote:
> On Sat, 17 Jul 2021 09:18:50 -0500
> olcott <NoOne@NoWhere.com> wrote:
>
>> On 7/17/2021 8:37 AM, Mr Flibble wrote:
>>> On Sat, 17 Jul 2021 13:22:56 -0000 (UTC)
>>> Alan Mackenzie <acm@muc.de> wrote:
>>>> Not really - you don't have a universal halting decider here by
>>>> design. And even if you did, the signature wouldn't do anything to
>>>> prevent the existence of the programs which have an "invalid
>>>> relationship" with D.
>>>
>>> The point is that this "invalid relationship" is DETECTABLE by the
>>> black box decider. This "invalid relationship" only exists for
>>> programs which are deliberately designed to defeat the decider
>>> which are uninteresting cases because presumably we are using a
>>> decider to decide legitimate programs that have serve some useful
>>> purpose beyond the HP itself.
>>>
>>> /Flibble
>>>
>>
>> We might as well have a black box cure for cancer or a black box cure
>> for violence in the world. Unless you say how it works it don't count.
>
> You haven't shown how your x86 omnishambles works so it "don't count".
>
> /Flibble
>
Sure I have. Anyone that:
(a) knows the x86 language.
(b) knows that H acts is a pure x86 emulator until after it makes its
halt status decision.
(c) Understands that (b) means that H can screen out its own address
range from every execution trace basis of its halt status decision.
(d) Examines the x86 execution trace of the simulation of P(P) and see
that P provides no escape from its infinite recursion.
Knows that H(P,P)==0 is the correct halt status decision.
*Simulating partial halt decider H correctly decides that P(P) never
halts (V0)*
// 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()
{
Output("Input_Halts = ", H((u32)P, (u32)P));
}
_P()
[00000c36](01) 55 push ebp
[00000c37](02) 8bec mov ebp,esp
[00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
[00000c3c](01) 50 push eax
[00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
[00000c40](01) 51 push ecx
[00000c41](05) e820fdffff call 00000966 // call H
[00000c46](03) 83c408 add esp,+08
[00000c49](02) 85c0 test eax,eax
[00000c4b](02) 7402 jz 00000c4f
[00000c4d](02) ebfe jmp 00000c4d
[00000c4f](01) 5d pop ebp
[00000c50](01) c3 ret
Size in bytes:(0027) [00000c50]
_main()
[00000c56](01) 55 push ebp
[00000c57](02) 8bec mov ebp,esp
[00000c59](05) 68360c0000 push 00000c36
[00000c5e](05) 68360c0000 push 00000c36
[00000c63](05) e8fefcffff call 00000966
[00000c68](03) 83c408 add esp,+08
[00000c6b](01) 50 push eax
[00000c6c](05) 6857030000 push 00000357
[00000c71](05) e810f7ffff call 00000386
[00000c76](03) 83c408 add esp,+08
[00000c79](02) 33c0 xor eax,eax
[00000c7b](01) 5d pop ebp
[00000c7c](01) c3 ret
Size in bytes:(0039) [00000c7c]
machine stack stack machine assembly
address address data code language
======== ======== ======== ========= =============
[00000c56][0010172a][00000000] 55 push ebp
[00000c57][0010172a][00000000] 8bec mov ebp,esp
[00000c59][00101726][00000c36] 68360c0000 push 00000c36
[00000c5e][00101722][00000c36] 68360c0000 push 00000c36
[00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)
Begin Local Halt Decider Simulation at Machine Address:c36
[00000c36][002117ca][002117ce] 55 push ebp
[00000c37][002117ca][002117ce] 8bec mov ebp,esp
[00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
[00000c3c][002117c6][00000c36] 50 push eax
[00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][002117c2][00000c36] 51 push ecx
[00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)
[00000c36][0025c1f2][0025c1f6] 55 push ebp
[00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
[00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
[00000c3c][0025c1ee][00000c36] 50 push eax
[00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
[00000c40][0025c1ea][00000c36] 51 push ecx
[00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
Local Halt Decider: Infinite Recursion Detected Simulation Stopped
[00000c68][0010172a][00000000] 83c408 add esp,+08
[00000c6b][00101726][00000000] 50 push eax
[00000c6c][00101722][00000357] 6857030000 push 00000357
[00000c71][00101722][00000357] e810f7ffff call 00000386
Input_Halts = 0
[00000c76][0010172a][00000000] 83c408 add esp,+08
[00000c79][0010172a][00000000] 33c0 xor eax,eax
[00000c7b][0010172e][00100000] 5d pop ebp
[00000c7c][00101732][00000068] c3 ret
Number_of_User_Instructions(27)
Number of Instructions Executed(23721)
https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation
--
Copyright 2021 Pete Olcott
"Great spirits have always encountered violent opposition from mediocre
minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-07-17 06:57 -0700 |
| Message-ID | <b6a6efc3-61a3-483a-ab72-051b16b82247n@googlegroups.com> |
| In reply to | #36507 |
On Saturday, 17 July 2021 at 20:50:04 UTC+8, Mr Flibble wrote:
> If it is impossible for a decider to be referenced by a pathological
> program for the purposes of defeating the decider (see Strachey [1965])
> then the all currently extant proofs which rely on the Strachey
> contradiction become invalid.
>
> I have a theoretical design for such a decider which I am calling a
> black box decider as its internal mechanism of operation is unknown to
> that which is being decided; this does rely on simulating the candidate
> (program + input) which means the decision will be returned in FINITE
> time (even if this time exceeds the age of the universe in duration)
> rather than being UNDECIDABLE.
>
> Method:
>
> 1) A trusted operator creates a digital signature, S, by digitally
> signing the candidate program, P and its input, I.
> 2) Operator runs the black box decider, D, passing it P, I, and
> and S.
> 3) If S is invalid (i.e. isn't signed by a trusted operator) D will
> abort due to P being pathological (i.e. it is attempting to defeat D by
> referencing D).
> 4) If the candidate digital signature is valid the decider simulates
> the P+I to determine if P halts or not (how long this takes
> depends on the complexity of the simulator and the candidate so this may
> take a very long (but FINITE) time).
>
> D will then return one of THREE results to the operator:
>
> a) P halts;
> b) P does not halt;
> c) P is invalid (attempted to defeat the decider).
>
> Obviously this solution depends on the strength of the digital
> signature encryption being such that breaking it would exceed the
> time used to reach a decision for P.
>
> Halting Problem solved? Debatable. Currently extant proofs valid? Not
> so much.
>
> /Flibble
I guess you did not see my GUR
https://groups.google.com/g/comp.theory/c/3yP71I5puns
//---------------------------
// Example 2: U is an executable
/*
[Syn] U <prog>
U Decides whether the program <prog> will return or not,
[Return Status] non-zero: <prog> will return (Or, TM stops at final accept or reject states)
zero: otherwise (<prog> will not return)
*/
/*
Program: P.c
Build: gcc -o P P.c
*/
#include <stdlib.h>
void P() { // P always behaves not predicted by U
int r=system("U P");
if(r) {
for(;;) {}; // infinite loop
}
};
int main() {
P();
};
------
I do not need to look into your magic black box (or anyone's). Because I know
even super intelligent alien can not even built the correct halting decider.
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 15:17 +0100 |
| Message-ID | <20210717151754.000007e2@reddwarf.jmc> |
| In reply to | #36513 |
On Sat, 17 Jul 2021 06:57:26 -0700 (PDT) wij <wyniijj@gmail.com> wrote: > On Saturday, 17 July 2021 at 20:50:04 UTC+8, Mr Flibble wrote: > > If it is impossible for a decider to be referenced by a > > pathological program for the purposes of defeating the decider (see > > Strachey [1965]) then the all currently extant proofs which rely on > > the Strachey contradiction become invalid. > > > > I have a theoretical design for such a decider which I am calling a > > black box decider as its internal mechanism of operation is unknown > > to that which is being decided; this does rely on simulating the > > candidate (program + input) which means the decision will be > > returned in FINITE time (even if this time exceeds the age of the > > universe in duration) rather than being UNDECIDABLE. > > > > Method: > > > > 1) A trusted operator creates a digital signature, S, by digitally > > signing the candidate program, P and its input, I. > > 2) Operator runs the black box decider, D, passing it P, I, and > > and S. > > 3) If S is invalid (i.e. isn't signed by a trusted operator) D will > > abort due to P being pathological (i.e. it is attempting to defeat > > D by referencing D). > > 4) If the candidate digital signature is valid the decider > > simulates the P+I to determine if P halts or not (how long this > > takes depends on the complexity of the simulator and the candidate > > so this may take a very long (but FINITE) time). > > > > D will then return one of THREE results to the operator: > > > > a) P halts; > > b) P does not halt; > > c) P is invalid (attempted to defeat the decider). > > > > Obviously this solution depends on the strength of the digital > > signature encryption being such that breaking it would exceed the > > time used to reach a decision for P. > > > > Halting Problem solved? Debatable. Currently extant proofs valid? > > Not so much. > > > > /Flibble > > I guess you did not see my GUR Sorry pal but you posted that 8 minutes AFTER my post so I win. https://groups.google.com/g/comp.theory/c/3cul2pw_uhU /Flibble
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-07-17 07:36 -0700 |
| Message-ID | <bf53f037-611d-41fa-bdeb-4d21164260c8n@googlegroups.com> |
| In reply to | #36517 |
On Saturday, 17 July 2021 at 22:17:57 UTC+8, Mr Flibble wrote: > On Sat, 17 Jul 2021 06:57:26 -0700 (PDT) > wij <wyn...@gmail.com> wrote: > > > On Saturday, 17 July 2021 at 20:50:04 UTC+8, Mr Flibble wrote: > > > If it is impossible for a decider to be referenced by a > > > pathological program for the purposes of defeating the decider (see > > > Strachey [1965]) then the all currently extant proofs which rely on > > > the Strachey contradiction become invalid. > > > > > > I have a theoretical design for such a decider which I am calling a > > > black box decider as its internal mechanism of operation is unknown > > > to that which is being decided; this does rely on simulating the > > > candidate (program + input) which means the decision will be > > > returned in FINITE time (even if this time exceeds the age of the > > > universe in duration) rather than being UNDECIDABLE. > > > > > > Method: > > > > > > 1) A trusted operator creates a digital signature, S, by digitally > > > signing the candidate program, P and its input, I. > > > 2) Operator runs the black box decider, D, passing it P, I, and > > > and S. > > > 3) If S is invalid (i.e. isn't signed by a trusted operator) D will > > > abort due to P being pathological (i.e. it is attempting to defeat > > > D by referencing D). > > > 4) If the candidate digital signature is valid the decider > > > simulates the P+I to determine if P halts or not (how long this > > > takes depends on the complexity of the simulator and the candidate > > > so this may take a very long (but FINITE) time). > > > > > > D will then return one of THREE results to the operator: > > > > > > a) P halts; > > > b) P does not halt; > > > c) P is invalid (attempted to defeat the decider). > > > > > > Obviously this solution depends on the strength of the digital > > > signature encryption being such that breaking it would exceed the > > > time used to reach a decision for P. > > > > > > Halting Problem solved? Debatable. Currently extant proofs valid? > > > Not so much. > > > > > > /Flibble > > > > I guess you did not see my GUR > Sorry pal but you posted that 8 minutes AFTER my post so I win. > > https://groups.google.com/g/comp.theory/c/3cul2pw_uhU > > /Flibble I did not post for you, kid. You win boo. General Undecidable Rule https://groups.google.com/g/comp.theory/c/3yP71I5puns
[toc] | [prev] | [standalone]
Page 6 of 6 — ← Prev page 1 2 3 4 5 [6]
Back to top | Article view | comp.theory
csiph-web