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 | 20 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 1 of 6 [1] 2 3 4 5 6 Next page →
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 13:50 +0100 |
| Subject | Halting Problem Solved? (Black Box Decider Theory) V2 |
| Message-ID | <20210717135003.00000fdc@reddwarf.jmc> |
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
[toc] | [next] | [standalone]
| From | Alan Mackenzie <acm@muc.de> |
|---|---|
| Date | 2021-07-17 13:22 +0000 |
| Message-ID | <sculjg$1q6c$6@news.muc.de> |
| In reply to | #36507 |
Mr Flibble <flibble@reddwarf.jmc> 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. There is no such thing as a "pathological program" in this sense. Every program either terminates or does not terminate. The only thing you could designate as "pathological" would be the relationship between the program and your black box, not the program itself. > 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. The black-box approach won't help you. The theorem rules out a _universal_ halt decider, that means a decider which decides _any_ program. There will be programs which confound your black box, despite your attempts to make it difficult to construct these - they still exist. And for those programs, your black box will return the wrong result. > 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). So, D isn't a halt decider, because there are programs for which it fails to return the correct yes/no result. Note, again, that in case c), there is nothing invalid about the program itself; it will run and either halt or not halt. It is the relationship between P and D that you are calling "invalid". I would go further and say that it is D which is invalid, since it cannot perform its purported function. > 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. 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. > Halting Problem solved? Debatable. Not really. You should really get into a proof of the halting problem theorem and _understand_ it. > Currently extant proofs valid? Not so much. These proofs remain totally valid. Since they do not depend on the internal workings of the purported decider, no amount of cleverness and deviousness in this area is going to make the slightest difference. This is what is so baffling Olcott, due to his inability to understand the concept of a proof. You are a computer science graduate, right? Surely, unlike Olcott, you do understand the concept of a proof, and that the halting problem theorem is proven? > /Flibble -- Alan Mackenzie (Nuremberg, Germany).
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 14:37 +0100 |
| Message-ID | <20210717143722.00007f34@reddwarf.jmc> |
| In reply to | #36508 |
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
[toc] | [prev] | [next] | [standalone]
| From | Alan Mackenzie <acm@muc.de> |
|---|---|
| Date | 2021-07-17 13:59 +0000 |
| Message-ID | <scunn6$1q6c$7@news.muc.de> |
| In reply to | #36510 |
Mr Flibble <flibble@reddwarf.jmc> 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. I think, but I'm not sure, that such relationships cannot be detected, that it's another one of these limitation theorems. Ben could probably say more on this. > This "invalid relationship" only exists for programs which are > deliberately designed to defeat the decider .... Not at all. There will be random programs, not deliberately designed, which will also have such a relationship with the purported 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. 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. None of this has any relevance for the theoremhood of the halting problem result itself. > /Flibble -- Alan Mackenzie (Nuremberg, Germany).
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 15:06 +0100 |
| Message-ID | <20210717150602.00003bc6@reddwarf.jmc> |
| In reply to | #36514 |
On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) Alan Mackenzie <acm@muc.de> wrote: > Mr Flibble <flibble@reddwarf.jmc> 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. > > I think, but I'm not sure, that such relationships cannot be detected, > that it's another one of these limitation theorems. Ben could > probably say more on this. > > > This "invalid relationship" only exists for programs which are > > deliberately designed to defeat the decider .... > > Not at all. There will be random programs, not deliberately designed, > which will also have such a relationship with the purported 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. > > 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. > > 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. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-17 09:17 -0500 |
| Message-ID | <R56dnVROjoDwe2_9nZ2dnUU7-X_NnZ2d@giganews.com> |
| In reply to | #36515 |
On 7/17/2021 9:06 AM, Mr Flibble wrote: > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > Alan Mackenzie <acm@muc.de> wrote: > >> Mr Flibble <flibble@reddwarf.jmc> 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. >> >> I think, but I'm not sure, that such relationships cannot be detected, >> that it's another one of these limitation theorems. Ben could >> probably say more on this. >> >>> This "invalid relationship" only exists for programs which are >>> deliberately designed to defeat the decider .... >> >> Not at all. There will be random programs, not deliberately designed, >> which will also have such a relationship with the purported 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. >> >> 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. >> >> 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. > > /Flibble > This was my idea 17 years ago. On Sunday, September 5, 2004 at 11:21:57 AM UTC-5, Peter Olcott wrote: > The Liar Paradox can be shown to be nothing more than > a incorrectly formed statement because of its pathological > self-reference. The Halting Problem can only exist because > of this same sort of pathological self-reference. > > The primary benefit of solving the Halting Problem was to > detect programs that failed to halt, thus were incorrect. > Pathological self-reference can also be viewed as a form > of error. If the Halting Problem is redefined (which does not > refute anyone), then this redefined problem can be easily > solved. > > Now we have three possible correct results: > (a) Halts > (b) Does Not Halt > (c) Pathological Self Reference to Halt > > Compared to my prior claims, this one seem trivial and > obvious. Possibly this claim adds a slight nuance to the > problem that has not been widely discussed before. > If we construe pathological self-reference as another > error condition, then this does remove the impossibility > of creating a useful tool. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Alan Mackenzie <acm@muc.de> |
|---|---|
| Date | 2021-07-17 14:20 +0000 |
| Message-ID | <scuovq$1q6c$8@news.muc.de> |
| In reply to | #36515 |
Mr Flibble <flibble@reddwarf.jmc> wrote: > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > Alan Mackenzie <acm@muc.de> wrote: >> Mr Flibble <flibble@reddwarf.jmc> 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. >> I think, but I'm not sure, that such relationships cannot be detected, >> that it's another one of these limitation theorems. Ben could >> probably say more on this. >> > This "invalid relationship" only exists for programs which are >> > deliberately designed to defeat the decider .... >> Not at all. There will be random programs, not deliberately designed, >> which will also have such a relationship with the purported 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. >> 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. >> 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. Let me stress again that there is nothing invalid or pathological about these programs, and they can run and halt or not halt like any other program. It is only in their relationship with H where they are special, in that H is unable to determine their halting status correctly. That's assuming it's possible for H to single out such programs. I don't know if this is possible in the general case, but I suspect it's not. Again, Ben or Richard might know more about this. But all this is moving away from the halting problem. > /Flibble -- Alan Mackenzie (Nuremberg, Germany).
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 15:24 +0100 |
| Message-ID | <20210717152448.00006958@reddwarf.jmc> |
| In reply to | #36520 |
On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) Alan Mackenzie <acm@muc.de> wrote: > Mr Flibble <flibble@reddwarf.jmc> wrote: > > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > > Alan Mackenzie <acm@muc.de> wrote: > > >> Mr Flibble <flibble@reddwarf.jmc> 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. > > >> I think, but I'm not sure, that such relationships cannot be > >> detected, that it's another one of these limitation theorems. Ben > >> could probably say more on this. > > >> > This "invalid relationship" only exists for programs which are > >> > deliberately designed to defeat the decider .... > > >> Not at all. There will be random programs, not deliberately > >> designed, which will also have such a relationship with the > >> purported 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. > > >> 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. > > >> 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. > > Let me stress again that there is nothing invalid or pathological > about these programs, and they can run and halt or not halt like any > other program. It is only in their relationship with H where they > are special, in that H is unable to determine their halting status > correctly. > > That's assuming it's possible for H to single out such programs. I > don't know if this is possible in the general case, but I suspect > it's not. Again, Ben or Richard might know more about this. > > But all this is moving away from the halting problem. Disagree: as the decider is a black box if it can always detect when it is being invoked, either directly by the trusted operator or indirectly by P which does not have the trusted operator's private key in order to digitally sign P and I that is passed to the decider. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Alan Mackenzie <acm@muc.de> |
|---|---|
| Date | 2021-07-17 14:34 +0000 |
| Message-ID | <scupqd$1q6c$9@news.muc.de> |
| In reply to | #36521 |
Mr Flibble <flibble@reddwarf.jmc> wrote: > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > Alan Mackenzie <acm@muc.de> wrote: >> Mr Flibble <flibble@reddwarf.jmc> wrote: >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) >> > Alan Mackenzie <acm@muc.de> wrote: >> >> Mr Flibble <flibble@reddwarf.jmc> 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. >> >> I think, but I'm not sure, that such relationships cannot be >> >> detected, that it's another one of these limitation theorems. Ben >> >> could probably say more on this. >> >> > This "invalid relationship" only exists for programs which are >> >> > deliberately designed to defeat the decider .... >> >> Not at all. There will be random programs, not deliberately >> >> designed, which will also have such a relationship with the >> >> purported 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. >> >> 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. >> >> 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. >> Let me stress again that there is nothing invalid or pathological >> about these programs, and they can run and halt or not halt like any >> other program. It is only in their relationship with H where they >> are special, in that H is unable to determine their halting status >> correctly. >> That's assuming it's possible for H to single out such programs. I >> don't know if this is possible in the general case, but I suspect >> it's not. Again, Ben or Richard might know more about this. >> But all this is moving away from the halting problem. > Disagree: as the decider is a black box if it can always detect when it > is being invoked, either directly by the trusted operator or indirectly > by P which does not have the trusted operator's private key in order to > digitally sign P and I that is passed to the decider. P might contain a copy of D's algorithm (with or without the key stuff), and indeed P might contain a copy of the private key. Such programs _exist_, whether or not we could as humans create them. As I say, I don't think it's possible for D to detect an algorithm which does the same as D. But in any case, D is not behaving as a universal halting detector, in that it doesn't return halts/doesn't halt for all input programs. > /Flibble -- Alan Mackenzie (Nuremberg, Germany).
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 15:38 +0100 |
| Message-ID | <20210717153827.00006057@reddwarf.jmc> |
| In reply to | #36523 |
On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) Alan Mackenzie <acm@muc.de> wrote: > Mr Flibble <flibble@reddwarf.jmc> wrote: > > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > > Alan Mackenzie <acm@muc.de> wrote: > > >> Mr Flibble <flibble@reddwarf.jmc> wrote: > >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > >> > Alan Mackenzie <acm@muc.de> wrote: > > >> >> Mr Flibble <flibble@reddwarf.jmc> 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. > > >> >> I think, but I'm not sure, that such relationships cannot be > >> >> detected, that it's another one of these limitation theorems. > >> >> Ben could probably say more on this. > > >> >> > This "invalid relationship" only exists for programs which are > >> >> > deliberately designed to defeat the decider .... > > >> >> Not at all. There will be random programs, not deliberately > >> >> designed, which will also have such a relationship with the > >> >> purported 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. > > >> >> 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. > >> >> > > >> >> 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. > > >> Let me stress again that there is nothing invalid or pathological > >> about these programs, and they can run and halt or not halt like > >> any other program. It is only in their relationship with H where > >> they are special, in that H is unable to determine their halting > >> status correctly. > > >> That's assuming it's possible for H to single out such programs. I > >> don't know if this is possible in the general case, but I suspect > >> it's not. Again, Ben or Richard might know more about this. > > >> But all this is moving away from the halting problem. > > > Disagree: as the decider is a black box if it can always detect > > when it is being invoked, either directly by the trusted operator > > or indirectly by P which does not have the trusted operator's > > private key in order to digitally sign P and I that is passed to > > the decider. > > P might contain a copy of D's algorithm (with or without the key > stuff), and indeed P might contain a copy of the private key. Such > programs _exist_, whether or not we could as humans create them. As > I say, I don't think it's possible for D to detect an algorithm which > does the same as D. > > But in any case, D is not behaving as a universal halting detector, in > that it doesn't return halts/doesn't halt for all input programs. I suggest you read up on what constitutes a black box: if the black box's algorithm has been copied then it is no longer a black box. https://en.wikipedia.org/wiki/Black_box /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Alan Mackenzie <acm@muc.de> |
|---|---|
| Date | 2021-07-17 14:45 +0000 |
| Message-ID | <scuqe7$1q6c$11@news.muc.de> |
| In reply to | #36527 |
Mr Flibble <flibble@reddwarf.jmc> wrote: > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) > Alan Mackenzie <acm@muc.de> wrote: >> Mr Flibble <flibble@reddwarf.jmc> wrote: >> > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) >> > Alan Mackenzie <acm@muc.de> wrote: >> >> Mr Flibble <flibble@reddwarf.jmc> wrote: >> >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) >> >> > Alan Mackenzie <acm@muc.de> wrote: >> >> >> Mr Flibble <flibble@reddwarf.jmc> 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. >> >> >> I think, but I'm not sure, that such relationships cannot be >> >> >> detected, that it's another one of these limitation theorems. >> >> >> Ben could probably say more on this. >> >> >> > This "invalid relationship" only exists for programs which are >> >> >> > deliberately designed to defeat the decider .... >> >> >> Not at all. There will be random programs, not deliberately >> >> >> designed, which will also have such a relationship with the >> >> >> purported 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. >> >> >> 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. >> >> >> 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. >> >> Let me stress again that there is nothing invalid or pathological >> >> about these programs, and they can run and halt or not halt like >> >> any other program. It is only in their relationship with H where >> >> they are special, in that H is unable to determine their halting >> >> status correctly. >> >> That's assuming it's possible for H to single out such programs. I >> >> don't know if this is possible in the general case, but I suspect >> >> it's not. Again, Ben or Richard might know more about this. >> >> But all this is moving away from the halting problem. >> > Disagree: as the decider is a black box if it can always detect >> > when it is being invoked, either directly by the trusted operator >> > or indirectly by P which does not have the trusted operator's >> > private key in order to digitally sign P and I that is passed to >> > the decider. >> P might contain a copy of D's algorithm (with or without the key >> stuff), and indeed P might contain a copy of the private key. Such >> programs _exist_, whether or not we could as humans create them. As >> I say, I don't think it's possible for D to detect an algorithm which >> does the same as D. >> But in any case, D is not behaving as a universal halting detector, in >> that it doesn't return halts/doesn't halt for all input programs. > I suggest you read up on what constitutes a black box: if the black > box's algorithm has been copied then it is no longer a black box. OK, then black boxes are, at this level of theory, not possible objects. Note I didn't say "has been copied", but "contains a copy", i.e. just randomly happens to match up. Such randomly matching programs exist. > /Flibble -- Alan Mackenzie (Nuremberg, Germany).
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 15:53 +0100 |
| Message-ID | <20210717155335.000025ff@reddwarf.jmc> |
| In reply to | #36529 |
On Sat, 17 Jul 2021 14:45:27 -0000 (UTC) Alan Mackenzie <acm@muc.de> wrote: > Mr Flibble <flibble@reddwarf.jmc> wrote: > > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) > > Alan Mackenzie <acm@muc.de> wrote: > > >> Mr Flibble <flibble@reddwarf.jmc> wrote: > >> > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > >> > Alan Mackenzie <acm@muc.de> wrote: > > >> >> Mr Flibble <flibble@reddwarf.jmc> wrote: > >> >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > >> >> > Alan Mackenzie <acm@muc.de> wrote: > > >> >> >> Mr Flibble <flibble@reddwarf.jmc> 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. > > >> >> >> I think, but I'm not sure, that such relationships cannot be > >> >> >> detected, that it's another one of these limitation theorems. > >> >> >> Ben could probably say more on this. > > >> >> >> > This "invalid relationship" only exists for programs which > >> >> >> > are deliberately designed to defeat the decider .... > >> >> >> > > > >> >> >> Not at all. There will be random programs, not deliberately > >> >> >> designed, which will also have such a relationship with the > >> >> >> purported 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. > >> >> >> > > > >> >> >> 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. > > > >> >> >> 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. > > >> >> Let me stress again that there is nothing invalid or > >> >> pathological about these programs, and they can run and halt or > >> >> not halt like any other program. It is only in their > >> >> relationship with H where they are special, in that H is unable > >> >> to determine their halting status correctly. > > >> >> That's assuming it's possible for H to single out such > >> >> programs. I don't know if this is possible in the general > >> >> case, but I suspect it's not. Again, Ben or Richard might know > >> >> more about this. > > >> >> But all this is moving away from the halting problem. > > >> > Disagree: as the decider is a black box if it can always detect > >> > when it is being invoked, either directly by the trusted operator > >> > or indirectly by P which does not have the trusted operator's > >> > private key in order to digitally sign P and I that is passed to > >> > the decider. > > >> P might contain a copy of D's algorithm (with or without the key > >> stuff), and indeed P might contain a copy of the private key. Such > >> programs _exist_, whether or not we could as humans create them. > >> As I say, I don't think it's possible for D to detect an algorithm > >> which does the same as D. > > >> But in any case, D is not behaving as a universal halting > >> detector, in that it doesn't return halts/doesn't halt for all > >> input programs. > > > I suggest you read up on what constitutes a black box: if the black > > box's algorithm has been copied then it is no longer a black box. > > OK, then black boxes are, at this level of theory, not possible > objects. Note I didn't say "has been copied", but "contains a copy", > i.e. just randomly happens to match up. Such randomly matching > programs exist. That assumes that the black box decider cannot detect when P and I are being passed to something equivalent to the black box; you know what they say about assumptions, right? The black box decider could certainly detect if P and I are being passed to something opaque and treat that as pathological behavior. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | Alan Mackenzie <acm@muc.de> |
|---|---|
| Date | 2021-07-17 15:12 +0000 |
| Message-ID | <scus0q$1q6c$12@news.muc.de> |
| In reply to | #36531 |
Mr Flibble <flibble@reddwarf.jmc> wrote: > On Sat, 17 Jul 2021 14:45:27 -0000 (UTC) > Alan Mackenzie <acm@muc.de> wrote: >> Mr Flibble <flibble@reddwarf.jmc> wrote: >> > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) >> > Alan Mackenzie <acm@muc.de> wrote: >> >> Mr Flibble <flibble@reddwarf.jmc> wrote: >> >> > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) >> >> > Alan Mackenzie <acm@muc.de> wrote: >> >> >> Mr Flibble <flibble@reddwarf.jmc> wrote: >> >> >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) >> >> >> > Alan Mackenzie <acm@muc.de> wrote: >> >> >> >> Mr Flibble <flibble@reddwarf.jmc> 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. >> >> >> >> I think, but I'm not sure, that such relationships cannot be >> >> >> >> detected, that it's another one of these limitation theorems. >> >> >> >> Ben could probably say more on this. >> >> >> >> > This "invalid relationship" only exists for programs which >> >> >> >> > are deliberately designed to defeat the decider .... >> >> >> >> Not at all. There will be random programs, not deliberately >> >> >> >> designed, which will also have such a relationship with the >> >> >> >> purported 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. >> >> >> >> 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. >> >> >> >> 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. >> >> >> Let me stress again that there is nothing invalid or >> >> >> pathological about these programs, and they can run and halt or >> >> >> not halt like any other program. It is only in their >> >> >> relationship with H where they are special, in that H is unable >> >> >> to determine their halting status correctly. >> >> >> That's assuming it's possible for H to single out such >> >> >> programs. I don't know if this is possible in the general >> >> >> case, but I suspect it's not. Again, Ben or Richard might know >> >> >> more about this. >> >> >> But all this is moving away from the halting problem. >> >> > Disagree: as the decider is a black box if it can always detect >> >> > when it is being invoked, either directly by the trusted operator >> >> > or indirectly by P which does not have the trusted operator's >> >> > private key in order to digitally sign P and I that is passed to >> >> > the decider. >> >> P might contain a copy of D's algorithm (with or without the key >> >> stuff), and indeed P might contain a copy of the private key. Such >> >> programs _exist_, whether or not we could as humans create them. >> >> As I say, I don't think it's possible for D to detect an algorithm >> >> which does the same as D. >> >> But in any case, D is not behaving as a universal halting >> >> detector, in that it doesn't return halts/doesn't halt for all >> >> input programs. >> > I suggest you read up on what constitutes a black box: if the black >> > box's algorithm has been copied then it is no longer a black box. >> OK, then black boxes are, at this level of theory, not possible >> objects. Note I didn't say "has been copied", but "contains a copy", >> i.e. just randomly happens to match up. Such randomly matching >> programs exist. > That assumes that the black box decider cannot detect when P and I are > being passed to something equivalent to the black box; Again, I'm beyond the limits of my knowledge, but I think it's a theorem that it is not possible to determine in general that two turing machines have the same functionality. In that case, the black box decider could not recognise something which happens to be a copy of its essentials. > you know what they say about assumptions, right? Indeed. You've been doing a fair amount of it yourself in constructing this black box idea. ;-) > The black box decider could certainly detect if P and I are being > passed to something opaque and treat that as pathological behavior. It's not certain at all. See above. > /Flibble -- Alan Mackenzie (Nuremberg, Germany).
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-07-17 11:53 -0500 |
| Subject | Re: Halting Problem Solved? (Black Box Decider Theory) [ Rice's Theorem ] |
| Message-ID | <N6ydnWAjqIuIlm79nZ2dnUU7-d-dnZ2d@giganews.com> |
| In reply to | #36535 |
On 7/17/2021 10:12 AM, Alan Mackenzie wrote: > Mr Flibble <flibble@reddwarf.jmc> wrote: >> On Sat, 17 Jul 2021 14:45:27 -0000 (UTC) >> Alan Mackenzie <acm@muc.de> wrote: > >>> Mr Flibble <flibble@reddwarf.jmc> wrote: >>>> On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) >>>> Alan Mackenzie <acm@muc.de> wrote: > >>>>> Mr Flibble <flibble@reddwarf.jmc> wrote: >>>>>> On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) >>>>>> Alan Mackenzie <acm@muc.de> wrote: > >>>>>>> Mr Flibble <flibble@reddwarf.jmc> wrote: >>>>>>>> On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) >>>>>>>> Alan Mackenzie <acm@muc.de> wrote: > >>>>>>>>> Mr Flibble <flibble@reddwarf.jmc> 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. > >>>>>>>>> I think, but I'm not sure, that such relationships cannot be >>>>>>>>> detected, that it's another one of these limitation theorems. >>>>>>>>> Ben could probably say more on this. > >>>>>>>>>> This "invalid relationship" only exists for programs which >>>>>>>>>> are deliberately designed to defeat the decider .... > > >>>>>>>>> Not at all. There will be random programs, not deliberately >>>>>>>>> designed, which will also have such a relationship with the >>>>>>>>> purported 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. > > >>>>>>>>> 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. > > >>>>>>>>> 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. > >>>>>>> Let me stress again that there is nothing invalid or >>>>>>> pathological about these programs, and they can run and halt or >>>>>>> not halt like any other program. It is only in their >>>>>>> relationship with H where they are special, in that H is unable >>>>>>> to determine their halting status correctly. > >>>>>>> That's assuming it's possible for H to single out such >>>>>>> programs. I don't know if this is possible in the general >>>>>>> case, but I suspect it's not. Again, Ben or Richard might know >>>>>>> more about this. > >>>>>>> But all this is moving away from the halting problem. > >>>>>> Disagree: as the decider is a black box if it can always detect >>>>>> when it is being invoked, either directly by the trusted operator >>>>>> or indirectly by P which does not have the trusted operator's >>>>>> private key in order to digitally sign P and I that is passed to >>>>>> the decider. > >>>>> P might contain a copy of D's algorithm (with or without the key >>>>> stuff), and indeed P might contain a copy of the private key. Such >>>>> programs _exist_, whether or not we could as humans create them. >>>>> As I say, I don't think it's possible for D to detect an algorithm >>>>> which does the same as D. > >>>>> But in any case, D is not behaving as a universal halting >>>>> detector, in that it doesn't return halts/doesn't halt for all >>>>> input programs. > >>>> I suggest you read up on what constitutes a black box: if the black >>>> box's algorithm has been copied then it is no longer a black box. > >>> OK, then black boxes are, at this level of theory, not possible >>> objects. Note I didn't say "has been copied", but "contains a copy", >>> i.e. just randomly happens to match up. Such randomly matching >>> programs exist. > >> That assumes that the black box decider cannot detect when P and I are >> being passed to something equivalent to the black box; > > Again, I'm beyond the limits of my knowledge, but I think it's a theorem > that it is not possible to determine in general that two turing machines > have the same functionality. In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable. A semantic property is one about the program's behavior (for instance, does the program terminate for all inputs), unlike a syntactic property (for instance, does the program contain an if-then-else statement). https://en.wikipedia.org/wiki/Rice%27s_theorem > In that case, the black box decider could > not recognise something which happens to be a copy of its essentials. > >> you know what they say about assumptions, right? > > Indeed. You've been doing a fair amount of it yourself in constructing > this black box idea. ;-) > >> The black box decider could certainly detect if P and I are being >> passed to something opaque and treat that as pathological behavior. > > It's not certain at all. See above. > >> /Flibble > -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-07-17 20:38 +0100 |
| Message-ID | <87zgukn335.fsf@bsb.me.uk> |
| In reply to | #36535 |
Alan Mackenzie <acm@muc.de> writes: > Mr Flibble <flibble@reddwarf.jmc> wrote: >> That assumes that the black box decider cannot detect when P and I are >> being passed to something equivalent to the black box; > > Again, I'm beyond the limits of my knowledge, but I think it's a theorem > that it is not possible to determine in general that two turing machines > have the same functionality. Indeed there is. > In that case, the black box decider could > not recognise something which happens to be a copy of its essentials. No algorithm can tell if the input includes (in whole or in part) a program functionally equivalent to itself. A decider could be written to detect the exact "hat" construction that is used in one or other proof. It could even detect an infinite number of variations of that pattern, but it can't detect them all. It would be very hard to do in practice because there is a sort of quine involved here, but I'm pretty sure it's possible for at least an infinite number of such patterns. But that's not nearly enough. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-07-17 08:04 -0700 |
| Message-ID | <dd09ea79-1e68-476a-8bf0-407341d5bd56n@googlegroups.com> |
| In reply to | #36527 |
On Saturday, 17 July 2021 at 22:38:30 UTC+8, Mr Flibble wrote: > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) > Alan Mackenzie <a...@muc.de> wrote: > > > Mr Flibble <fli...@reddwarf.jmc> wrote: > > > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > > > Alan Mackenzie <a...@muc.de> wrote: > > > > >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > > >> > Alan Mackenzie <a...@muc.de> wrote: > > > > >> >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > >> >> > On Sat, 17 Jul 2021 13:22:56 -0000 (UTC) > > >> >> > Alan Mackenzie <a...@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. > > > > >> >> I think, but I'm not sure, that such relationships cannot be > > >> >> detected, that it's another one of these limitation theorems. > > >> >> Ben could probably say more on this. > > > > >> >> > This "invalid relationship" only exists for programs which are > > >> >> > deliberately designed to defeat the decider .... > > > > >> >> Not at all. There will be random programs, not deliberately > > >> >> designed, which will also have such a relationship with the > > >> >> purported 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. > > > > >> >> 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. > > >> >> > > > > >> >> 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. > > > > >> Let me stress again that there is nothing invalid or pathological > > >> about these programs, and they can run and halt or not halt like > > >> any other program. It is only in their relationship with H where > > >> they are special, in that H is unable to determine their halting > > >> status correctly. > > > > >> That's assuming it's possible for H to single out such programs. I > > >> don't know if this is possible in the general case, but I suspect > > >> it's not. Again, Ben or Richard might know more about this. > > > > >> But all this is moving away from the halting problem. > > > > > Disagree: as the decider is a black box if it can always detect > > > when it is being invoked, either directly by the trusted operator > > > or indirectly by P which does not have the trusted operator's > > > private key in order to digitally sign P and I that is passed to > > > the decider. > > > > P might contain a copy of D's algorithm (with or without the key > > stuff), and indeed P might contain a copy of the private key. Such > > programs _exist_, whether or not we could as humans create them. As > > I say, I don't think it's possible for D to detect an algorithm which > > does the same as D. > > > > But in any case, D is not behaving as a universal halting detector, in > > that it doesn't return halts/doesn't halt for all input programs. > I suggest you read up on what constitutes a black box: if the black > box's algorithm has been copied then it is no longer a black box. > > https://en.wikipedia.org/wiki/Black_box > > /Flibble Quote carefully, kid. You do not seem to read it. ...a black box is a system which can be viewed in terms of its inputs and outputs (or transfer characteristics),... This is illustrated in Example 2 https://groups.google.com/g/comp.theory/c/3yP71I5puns
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 16:12 +0100 |
| Message-ID | <20210717161250.00006fab@reddwarf.jmc> |
| In reply to | #36533 |
On Sat, 17 Jul 2021 08:04:56 -0700 (PDT) wij <wyniijj@gmail.com> wrote: > On Saturday, 17 July 2021 at 22:38:30 UTC+8, Mr Flibble wrote: > > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) > > Alan Mackenzie <a...@muc.de> wrote: > > > > > Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > > > > Alan Mackenzie <a...@muc.de> wrote: > > > > > > >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > > > >> > Alan Mackenzie <a...@muc.de> wrote: > > > > > > >> >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > >> >> > On Sat, 17 Jul 2021 13:22:56 -0000 (UTC) > > > >> >> > Alan Mackenzie <a...@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. > > > > > > >> >> I think, but I'm not sure, that such relationships cannot > > > >> >> be detected, that it's another one of these limitation > > > >> >> theorems. Ben could probably say more on this. > > > > > > >> >> > This "invalid relationship" only exists for programs > > > >> >> > which are deliberately designed to defeat the decider > > > >> >> > .... > > > > > > >> >> Not at all. There will be random programs, not deliberately > > > >> >> designed, which will also have such a relationship with the > > > >> >> purported 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. > > > > > > >> >> 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. > > > > > > >> >> 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. > > > > > > >> Let me stress again that there is nothing invalid or > > > >> pathological about these programs, and they can run and halt > > > >> or not halt like any other program. It is only in their > > > >> relationship with H where they are special, in that H is > > > >> unable to determine their halting status correctly. > > > > > > >> That's assuming it's possible for H to single out such > > > >> programs. I don't know if this is possible in the general > > > >> case, but I suspect it's not. Again, Ben or Richard might know > > > >> more about this. > > > > > > >> But all this is moving away from the halting problem. > > > > > > > Disagree: as the decider is a black box if it can always detect > > > > when it is being invoked, either directly by the trusted > > > > operator or indirectly by P which does not have the trusted > > > > operator's private key in order to digitally sign P and I that > > > > is passed to the decider. > > > > > > P might contain a copy of D's algorithm (with or without the key > > > stuff), and indeed P might contain a copy of the private key. > > > Such programs _exist_, whether or not we could as humans create > > > them. As I say, I don't think it's possible for D to detect an > > > algorithm which does the same as D. > > > > > > But in any case, D is not behaving as a universal halting > > > detector, in that it doesn't return halts/doesn't halt for all > > > input programs. > > I suggest you read up on what constitutes a black box: if the black > > box's algorithm has been copied then it is no longer a black box. > > > > https://en.wikipedia.org/wiki/Black_box > > > > /Flibble > > Quote carefully, kid. You do not seem to read it. > ...a black box is a system which can be viewed in terms of its inputs > and outputs (or transfer characteristics),... > > This is illustrated in Example 2 > https://groups.google.com/g/comp.theory/c/3yP71I5puns What you quoted does NOT contradict what I said. If you don't have anything of value to add to the discussion then it is best to just keep your fucking mouth shut. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-07-17 08:25 -0700 |
| Message-ID | <96f2ae27-54db-47c9-8401-3cf6efa4d121n@googlegroups.com> |
| In reply to | #36536 |
On Saturday, 17 July 2021 at 23:12:51 UTC+8, Mr Flibble wrote: > On Sat, 17 Jul 2021 08:04:56 -0700 (PDT) > wij <wyn...@gmail.com> wrote: > > > On Saturday, 17 July 2021 at 22:38:30 UTC+8, Mr Flibble wrote: > > > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) > > > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > > > > > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > > > > >> > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > >> >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > >> >> > On Sat, 17 Jul 2021 13:22:56 -0000 (UTC) > > > > >> >> > Alan Mackenzie <a...@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. > > > > > > > > >> >> I think, but I'm not sure, that such relationships cannot > > > > >> >> be detected, that it's another one of these limitation > > > > >> >> theorems. Ben could probably say more on this. > > > > > > > > >> >> > This "invalid relationship" only exists for programs > > > > >> >> > which are deliberately designed to defeat the decider > > > > >> >> > .... > > > > > > > > >> >> Not at all. There will be random programs, not deliberately > > > > >> >> designed, which will also have such a relationship with the > > > > >> >> purported 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. > > > > > > > > >> >> 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. > > > > > > > > >> >> 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. > > > > > > > > >> Let me stress again that there is nothing invalid or > > > > >> pathological about these programs, and they can run and halt > > > > >> or not halt like any other program. It is only in their > > > > >> relationship with H where they are special, in that H is > > > > >> unable to determine their halting status correctly. > > > > > > > > >> That's assuming it's possible for H to single out such > > > > >> programs. I don't know if this is possible in the general > > > > >> case, but I suspect it's not. Again, Ben or Richard might know > > > > >> more about this. > > > > > > > > >> But all this is moving away from the halting problem. > > > > > > > > > Disagree: as the decider is a black box if it can always detect > > > > > when it is being invoked, either directly by the trusted > > > > > operator or indirectly by P which does not have the trusted > > > > > operator's private key in order to digitally sign P and I that > > > > > is passed to the decider. > > > > > > > > P might contain a copy of D's algorithm (with or without the key > > > > stuff), and indeed P might contain a copy of the private key. > > > > Such programs _exist_, whether or not we could as humans create > > > > them. As I say, I don't think it's possible for D to detect an > > > > algorithm which does the same as D. > > > > > > > > But in any case, D is not behaving as a universal halting > > > > detector, in that it doesn't return halts/doesn't halt for all > > > > input programs. > > > I suggest you read up on what constitutes a black box: if the black > > > box's algorithm has been copied then it is no longer a black box. > > > > > > https://en.wikipedia.org/wiki/Black_box > > > > > > /Flibble > > > > Quote carefully, kid. You do not seem to read it. > > ...a black box is a system which can be viewed in terms of its inputs > > and outputs (or transfer characteristics),... > > > > This is illustrated in Example 2 > > https://groups.google.com/g/comp.theory/c/3yP71I5puns > What you quoted does NOT contradict what I said. If you don't have > anything of value to add to the discussion then it is best to just keep > your fucking mouth shut. > > /Flibble Feel losed? Be happy. A black box program can be copied, reused by invoking...etc. This is illustrated in Example 2 (do not feel shy) https://groups.google.com/g/comp.theory/c/3yP71I5puns
[toc] | [prev] | [next] | [standalone]
| From | Mr Flibble <flibble@reddwarf.jmc> |
|---|---|
| Date | 2021-07-17 16:28 +0100 |
| Message-ID | <20210717162805.000040d0@reddwarf.jmc> |
| In reply to | #36538 |
On Sat, 17 Jul 2021 08:25:12 -0700 (PDT) wij <wyniijj@gmail.com> wrote: > On Saturday, 17 July 2021 at 23:12:51 UTC+8, Mr Flibble wrote: > > On Sat, 17 Jul 2021 08:04:56 -0700 (PDT) > > wij <wyn...@gmail.com> wrote: > > > > > On Saturday, 17 July 2021 at 22:38:30 UTC+8, Mr Flibble wrote: > > > > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) > > > > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > > Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > > > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > > > > > > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > > > >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > > >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > > > > > >> > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > > > >> >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > > >> >> > On Sat, 17 Jul 2021 13:22:56 -0000 (UTC) > > > > > >> >> > Alan Mackenzie <a...@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. > > > > > > > > > > >> >> I think, but I'm not sure, that such relationships > > > > > >> >> cannot be detected, that it's another one of these > > > > > >> >> limitation theorems. Ben could probably say more on > > > > > >> >> this. > > > > > > > > > > >> >> > This "invalid relationship" only exists for programs > > > > > >> >> > which are deliberately designed to defeat the decider > > > > > >> >> > .... > > > > > > > > > > >> >> Not at all. There will be random programs, not > > > > > >> >> deliberately designed, which will also have such a > > > > > >> >> relationship with the purported 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. > > > > > > > > > > >> >> 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. > > > > > > > > > > >> >> 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. > > > > > > > > > > >> Let me stress again that there is nothing invalid or > > > > > >> pathological about these programs, and they can run and > > > > > >> halt or not halt like any other program. It is only in > > > > > >> their relationship with H where they are special, in that > > > > > >> H is unable to determine their halting status correctly. > > > > > > > > > > >> That's assuming it's possible for H to single out such > > > > > >> programs. I don't know if this is possible in the general > > > > > >> case, but I suspect it's not. Again, Ben or Richard might > > > > > >> know more about this. > > > > > > > > > > >> But all this is moving away from the halting problem. > > > > > > > > > > > Disagree: as the decider is a black box if it can always > > > > > > detect when it is being invoked, either directly by the > > > > > > trusted operator or indirectly by P which does not have the > > > > > > trusted operator's private key in order to digitally sign P > > > > > > and I that is passed to the decider. > > > > > > > > > > P might contain a copy of D's algorithm (with or without the > > > > > key stuff), and indeed P might contain a copy of the private > > > > > key. Such programs _exist_, whether or not we could as humans > > > > > create them. As I say, I don't think it's possible for D to > > > > > detect an algorithm which does the same as D. > > > > > > > > > > But in any case, D is not behaving as a universal halting > > > > > detector, in that it doesn't return halts/doesn't halt for > > > > > all input programs. > > > > I suggest you read up on what constitutes a black box: if the > > > > black box's algorithm has been copied then it is no longer a > > > > black box. > > > > > > > > https://en.wikipedia.org/wiki/Black_box > > > > > > > > /Flibble > > > > > > Quote carefully, kid. You do not seem to read it. > > > ...a black box is a system which can be viewed in terms of its > > > inputs and outputs (or transfer characteristics),... > > > > > > This is illustrated in Example 2 > > > https://groups.google.com/g/comp.theory/c/3yP71I5puns > > What you quoted does NOT contradict what I said. If you don't have > > anything of value to add to the discussion then it is best to just > > keep your fucking mouth shut. > > > > /Flibble > > Feel losed? Be happy. > > A black box program can be copied, reused by invoking...etc. > > This is illustrated in Example 2 (do not feel shy) > https://groups.google.com/g/comp.theory/c/3yP71I5puns Except you are ignoring the fact that a digital signature from a trusted operator is one of the parameters to the black box so it cannot be "re-used by invoking etc" unless you have the trusted operator's private key. Again: best to keep your fucking mouth shut if you have nothing of value to add, pal. /Flibble
[toc] | [prev] | [next] | [standalone]
| From | wij <wyniijj@gmail.com> |
|---|---|
| Date | 2021-07-17 08:37 -0700 |
| Message-ID | <2f41a1cd-a042-484e-a3d7-ad03d945e287n@googlegroups.com> |
| In reply to | #36539 |
On Saturday, 17 July 2021 at 23:28:06 UTC+8, Mr Flibble wrote: > On Sat, 17 Jul 2021 08:25:12 -0700 (PDT) > wij <wyn...@gmail.com> wrote: > > > On Saturday, 17 July 2021 at 23:12:51 UTC+8, Mr Flibble wrote: > > > On Sat, 17 Jul 2021 08:04:56 -0700 (PDT) > > > wij <wyn...@gmail.com> wrote: > > > > > > > On Saturday, 17 July 2021 at 22:38:30 UTC+8, Mr Flibble wrote: > > > > > On Sat, 17 Jul 2021 14:34:53 -0000 (UTC) > > > > > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > > > > Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > > > > On Sat, 17 Jul 2021 14:20:42 -0000 (UTC) > > > > > > > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > > > > > >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > > > >> > On Sat, 17 Jul 2021 13:59:02 -0000 (UTC) > > > > > > >> > Alan Mackenzie <a...@muc.de> wrote: > > > > > > > > > > > > >> >> Mr Flibble <fli...@reddwarf.jmc> wrote: > > > > > > >> >> > On Sat, 17 Jul 2021 13:22:56 -0000 (UTC) > > > > > > >> >> > Alan Mackenzie <a...@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. > > > > > > > > > > > > >> >> I think, but I'm not sure, that such relationships > > > > > > >> >> cannot be detected, that it's another one of these > > > > > > >> >> limitation theorems. Ben could probably say more on > > > > > > >> >> this. > > > > > > > > > > > > >> >> > This "invalid relationship" only exists for programs > > > > > > >> >> > which are deliberately designed to defeat the decider > > > > > > >> >> > .... > > > > > > > > > > > > >> >> Not at all. There will be random programs, not > > > > > > >> >> deliberately designed, which will also have such a > > > > > > >> >> relationship with the purported 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. > > > > > > > > > > > > >> >> 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. > > > > > > > > > > > > >> >> 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. > > > > > > > > > > > > >> Let me stress again that there is nothing invalid or > > > > > > >> pathological about these programs, and they can run and > > > > > > >> halt or not halt like any other program. It is only in > > > > > > >> their relationship with H where they are special, in that > > > > > > >> H is unable to determine their halting status correctly. > > > > > > > > > > > > >> That's assuming it's possible for H to single out such > > > > > > >> programs. I don't know if this is possible in the general > > > > > > >> case, but I suspect it's not. Again, Ben or Richard might > > > > > > >> know more about this. > > > > > > > > > > > > >> But all this is moving away from the halting problem. > > > > > > > > > > > > > Disagree: as the decider is a black box if it can always > > > > > > > detect when it is being invoked, either directly by the > > > > > > > trusted operator or indirectly by P which does not have the > > > > > > > trusted operator's private key in order to digitally sign P > > > > > > > and I that is passed to the decider. > > > > > > > > > > > > P might contain a copy of D's algorithm (with or without the > > > > > > key stuff), and indeed P might contain a copy of the private > > > > > > key. Such programs _exist_, whether or not we could as humans > > > > > > create them. As I say, I don't think it's possible for D to > > > > > > detect an algorithm which does the same as D. > > > > > > > > > > > > But in any case, D is not behaving as a universal halting > > > > > > detector, in that it doesn't return halts/doesn't halt for > > > > > > all input programs. > > > > > I suggest you read up on what constitutes a black box: if the > > > > > black box's algorithm has been copied then it is no longer a > > > > > black box. > > > > > > > > > > https://en.wikipedia.org/wiki/Black_box > > > > > > > > > > /Flibble > > > > > > > > Quote carefully, kid. You do not seem to read it. > > > > ...a black box is a system which can be viewed in terms of its > > > > inputs and outputs (or transfer characteristics),... > > > > > > > > This is illustrated in Example 2 > > > > https://groups.google.com/g/comp.theory/c/3yP71I5puns > > > What you quoted does NOT contradict what I said. If you don't have > > > anything of value to add to the discussion then it is best to just > > > keep your fucking mouth shut. > > > > > > /Flibble > > > > Feel losed? Be happy. > > > > A black box program can be copied, reused by invoking...etc. > > > > This is illustrated in Example 2 (do not feel shy) > > https://groups.google.com/g/comp.theory/c/3yP71I5puns > Except you are ignoring the fact that a digital signature from a > trusted operator is one of the parameters to the black box so it cannot > be "re-used by invoking etc" unless you have the trusted operator's > private key. Again: best to keep your fucking mouth shut if you have > nothing of value to add, pal. > > /Flibble Halting problem H is supposed to be an utility program. It must be able to be reused. Or it does not qualified as a HP. No one need to see what H is inside: This is illustrated in Example 2 https://groups.google.com/g/comp.theory/c/3yP71I5puns Feel lost? Be happy.
[toc] | [prev] | [next] | [standalone]
Page 1 of 6 [1] 2 3 4 5 6 Next page →
Back to top | Article view | comp.theory
csiph-web