Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Alan Mackenzie <acm@muc.de> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Halting Problem Solved? (Black Box Decider Theory) V2 |
| Date | 2021-07-17 13:59 +0000 |
| Organization | muc.de e.V. |
| Message-ID | <scunn6$1q6c$7@news.muc.de> (permalink) |
| References | <20210717135003.00000fdc@reddwarf.jmc> <sculjg$1q6c$6@news.muc.de> <20210717143722.00007f34@reddwarf.jmc> |
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).
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
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
csiph-web