Halting problem erroneously defined

From	Mr Flibble <flibble@reddwarf.jmc>
Newsgroups	comp.theory
Subject	Halting problem erroneously defined
Message-ID	<20210715182217.00002c8c@reddwarf.jmc> (permalink)
Organization	Jupiter Mining Corp
Date	2021-07-15 18:22 +0100

Show all headers | View raw

Hi!

From Wikipedia Halting Problem page:

	For any program f that might determine if programs halt, a
	"pathological" program g, called with some input, can pass its
	own source and its input to f and then specifically do the
	opposite of what f predicts g will do. No f can exist that
	handles this case.

To me this looks like everyone is assuming that the halting problem is
undecidable based on a misunderstanding of the contradiction
crystallized by [Strachen 1965].

Strachen isn't saying the halting problem is undecidable, he is saying that
there is a contradiction that means that a decider can not be a part of
or called by that which is being decided. This doesn't mean that the
halting problem is not undecidable but it does mean that if that
Wikipedia extract is the current state of the art then nobody has proven
that the HP is undecidable, at least for non-"pathological" programs.

Olcott is on to something. :)

/Flibble

Back to comp.theory | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 18:22 +0100
  Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 12:42 -0500
    Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 18:48 +0100
      Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 19:00 +0100
        Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 13:04 -0500
          Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-15 19:09 +0100
            Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 13:17 -0500
      Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 13:01 -0500
  Re: Halting problem erroneously defined Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-07-15 20:08 +0100
    Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 15:57 -0500
      Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-15 23:06 +0100
        Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 18:00 -0500
          Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 01:29 +0100
            Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 19:59 -0500
              Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 02:49 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-15 21:43 -0500
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 01:29 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-17 11:05 -0500
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-18 02:36 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-19 10:09 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-19 08:18 -0700
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-20 01:38 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-20 09:29 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-20 09:17 -0700
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-21 01:28 +0100
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 21:57 -0600
    Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 13:25 +0100
      Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 08:56 -0500
    Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 13:33 +0100
      Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 09:28 -0500
      Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 14:44 +0000
        Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 09:52 -0500
          Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 16:39 +0000
            Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 12:13 -0500
              Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 18:26 +0100
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 12:41 -0500
                Re: Halting problem erroneously defined Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 19:37 +0100
              Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 11:53 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 13:39 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 12:52 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:40 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 13:57 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 15:09 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 14:30 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 16:06 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 16:09 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 17:24 -0500
                Re: Halting problem erroneously defined André G. Isaak <agisaak@gm.invalid> - 2021-07-16 16:48 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-17 10:22 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:24 -0600
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:09 -0600
                Re: Halting problem erroneously defined Jeff Barnett <jbb@notatt.com> - 2021-07-16 13:51 -0600
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:57 -0500
                Re: Halting problem erroneously defined Jeff Barnett <jbb@notatt.com> - 2021-07-16 16:34 -0600
              Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 18:25 +0000
                Re: Halting problem erroneously defined Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 19:29 +0100
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 18:59 +0000
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:42 -0500
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:22 -0500
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:33 -0500
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 20:19 +0000
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 15:34 -0500
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-16 21:30 +0000
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 16:57 -0500
                Re: Halting problem erroneously defined Alan Mackenzie <acm@muc.de> - 2021-07-17 09:39 +0000
                Re: Halting problem erroneously defined [AM] olcott <NoOne@NoWhere.com> - 2021-07-17 10:11 -0500
                Re: Halting problem erroneously defined [AM] Alan Mackenzie <acm@muc.de> - 2021-07-17 17:41 +0000
                Re: Halting problem erroneously defined [AM] olcott <NoOne@NoWhere.com> - 2021-07-17 13:26 -0500
              Re: Halting problem erroneously defined wij <wyniijj@gmail.com> - 2021-07-16 11:45 -0700
                Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-16 14:37 -0500
                Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:28 -0600
              Re: Halting problem erroneously defined Jeff Barnett <jbb@notatt.com> - 2021-07-16 13:31 -0600
          Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-17 22:06 -0600
  Re: Halting problem erroneously defined wij <wyniijj@gmail.com> - 2021-07-17 03:01 -0700
  Re: Halting problem erroneously defined Charlie-Boo <shymathguy@gmail.com> - 2021-07-19 07:35 -0700
    Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-19 15:45 -0500
      Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-19 20:44 -0700
  Re: Halting problem erroneously defined Charlie-Boo <shymathguy@gmail.com> - 2021-07-19 07:43 -0700
    Re: Halting problem erroneously defined olcott <NoOne@NoWhere.com> - 2021-07-19 15:49 -0500
      Re: Halting problem erroneously defined Richard Damon <Richard@Damon-Family.org> - 2021-07-19 20:46 -0700

csiph-web