Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #24542

Re: Architectural design of a halting problem solution

Subject Re: Architectural design of a halting problem solution
Newsgroups comp.theory
References <4o2dnVXM88fR6AXCnZ2dnUU7-K3NnZ2d@giganews.com>
From Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date 2020-10-27 20:03 +0000
Message-ID <MrCdnT6gAuuP4AXCnZ2dnUU78K2dnZ2d@brightview.co.uk> (permalink)

Show all headers | View raw


On 27/10/2020 19:30, olcott wrote:
> Intuitively, a decider should be a Turing machine that given an input,
> halts and either accepts or rejects, relaying its answer in one of many
> equivalent ways, such as halting at an ACCEPT or REJECT state, or
> leaving its answer on the output tape.Yuval Filmus
> https://cs.stackexchange.com/questions/84433/what-is-decider
>
> Yuval Filmus top 0.04% overall Assistant Professor in the Department of
> Computer Science at the Technion.
>
> It is common knowledge that a halt decider with the following
> architectural design can be thwarted by an input program that does the
> opposite of whatever the halt decider decides:
>
> The halt decider divides all of its inputs into:
> (a) HALTS
> (b) DOES_NOT_HALT

That's not an "architecural design" - it's part of the definition of a 
halt decider.  It's good though, that you seem to be finally admitting 
that the HP proof is correct.  The end of an era!!

You may not get the fame and credibility you longed for, but at least 
you can get on with the rest of your life.

>
> This brand new architectural design cannot be thwarted by the
> conventional self-referential halting problem trick. With this design
> there is no input that can be shown to be undecidable:
>
> The halt decider that divides all of its inputs into:
> (a) INPUT_PROGRAM_ABORTED_BECAUSE_NON_HALTING_BEHAVIOR_DETECTED
> (b) INPUT_PROGRAM_HAS_TERMINATED
>

Aha, some kind of "aborted because non-halting behaviour detected"
decider!  Unfortunately there are plenty of decision problems that /are/ 
decidable, including many whose domain is the same as that halting 
problem's.  Possibly if you made the definition of the your decision 
well defined, it could be one of those...

> The redefined halt decider UTM executes its subordinate UTM one state
> transition at a time until it detects non-halting behavior or its
> subordinate UTM has terminated normally.
>
> If the halt decider UTM detects non-halting behavior of its subordinate
> UTM it simply stops executing the subordinate and transitions to its own
> final state of ABORTED_NON_TERMINATING_BEHAVIOR.
>
> If the subordinate UTM terminates normally the halt decider UTM
> transitions to its own final state of SUBORDINATE_HAS_TERMINATED.
>

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


Thread

Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 14:30 -0500
  Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 13:46 -0600
    Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 15:02 -0500
  Re: Architectural design of a halting problem solution Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-27 20:03 +0000
    Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 15:13 -0500
      Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 14:34 -0600
        Re: Architectural design of a halting problem solution Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-27 21:11 +0000
          Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:27 -0500
            Re: Architectural design of a halting problem solution Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-27 21:33 +0000
              Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:57 -0500
            Re: Architectural design of a halting problem solution Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-10-27 14:44 -0700
              Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:54 -0500
                Re: Architectural design of a halting problem solution Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-10-27 15:07 -0700
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 18:43 -0500
            Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-27 21:45 -0400
              Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 21:28 -0500
                Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-27 22:48 -0400
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 21:55 -0500
                Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-28 09:04 -0400
                Re: Architectural design of a halting problem solution Mostowski Collapse <janburse@fastmail.fm> - 2020-10-28 14:13 +0100
                Re: Architectural design of a halting problem solution David Brown <david.brown@hesbynett.no> - 2020-10-28 15:12 +0100
                Re: Architectural design of a halting problem solution Mostowski Collapse <janburse@fastmail.fm> - 2020-10-28 14:13 +0100
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 18:18 -0500
            Re: Architectural design of a halting problem solution Alan Mackenzie <acm@muc.de> - 2020-10-28 09:38 +0000
              Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 17:54 -0500
                Re: Architectural design of a halting problem solution Alan Mackenzie <acm@muc.de> - 2020-10-29 06:59 +0000
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 07:28 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 07:35 -0500
        Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-27 16:23 -0500
          Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 22:49 -0600
            Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 00:05 -0500
              Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 23:25 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 00:31 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-27 23:55 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 17:50 -0500
                Re: Architectural design of a halting problem solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-28 23:27 +0000
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-28 21:09 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 00:45 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 07:18 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 07:30 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 11:05 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 10:55 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 12:52 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 11:58 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 13:25 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 12:56 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 14:13 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 13:50 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 15:18 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 14:52 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 16:18 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-30 08:53 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-30 10:55 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-31 08:28 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 09:53 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-31 09:23 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 10:35 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-31 09:44 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 11:03 -0500
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-11-01 07:46 -0700
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-11-01 12:12 -0600
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-11-01 12:45 -0600
                Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-31 14:46 -0400
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 13:57 -0500
                Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-31 16:00 -0400
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 15:34 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 15:42 -0500
                Re: Architectural design of a halting problem solution Alan Mackenzie <acm@muc.de> - 2020-10-31 21:07 +0000
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 16:19 -0500
                Re: Architectural design of a halting problem solution Alan Mackenzie <acm@muc.de> - 2020-10-31 21:33 +0000
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 16:50 -0500
                Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-31 18:31 -0400
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-10-31 17:50 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-10-31 19:53 -0400
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-10-31 19:19 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-10-31 21:19 -0400
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-10-31 22:22 -0400
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-10-31 21:36 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-10-31 22:18 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-11-01 08:19 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 08:40 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-01 16:11 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 12:18 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-01 19:50 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 14:09 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 14:38 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-01 21:32 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 15:54 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-02 00:46 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 19:05 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 19:10 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-11-01 21:57 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 22:33 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-11-02 08:53 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-02 08:04 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-11-02 10:45 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-02 03:00 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 22:32 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-02 20:55 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-02 15:20 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-02 16:20 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-02 01:16 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 19:28 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-02 03:15 +0000
                Re: Architectural design of a halting problem solution [ Adaptation of Ben's code simplifications ] olcott <NoOne@NoWhere.com> - 2020-11-01 22:20 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-02 03:02 +0000
                Re: Architectural design of a halting problem solution [ one paragraph says it all ] olcott <NoOne@NoWhere.com> - 2020-11-01 21:55 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 22:25 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-02 02:45 +0000
                Re: Architectural design of a halting problem solution [ non halting behavior detected ] olcott <NoOne@NoWhere.com> - 2020-11-01 23:14 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-02 03:12 -0800
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] André G. Isaak <agisaak@gm.invalid> - 2020-11-02 04:52 -0700
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-02 08:01 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] André G. Isaak <agisaak@gm.invalid> - 2020-11-02 08:12 -0700
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-11-02 10:23 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-02 07:58 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 14:02 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-11-01 17:52 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 17:59 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Richard Damon <Richard@Damon-Family.org> - 2020-11-01 21:38 -0500
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 21:05 -0600
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-02 00:17 +0000
                Re: Architectural design of a halting problem solution [ Bill the auto mechanic can fix your car ] olcott <NoOne@NoWhere.com> - 2020-11-01 19:53 -0600
                Re: Architectural design of a halting problem solution Alan Mackenzie <acm@muc.de> - 2020-11-01 08:29 +0000
                Re: Architectural design of a halting problem solution Richard Damon <Richard@Damon-Family.org> - 2020-10-31 18:28 -0400
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 17:42 -0500
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-31 15:47 -0500
                Re: Architectural design of a halting problem solution Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-10-29 13:13 -0700
                Re: Architectural design of a halting problem solution André G. Isaak <agisaak@gm.invalid> - 2020-10-29 14:46 -0600
                Re: Architectural design of a halting problem solution Andy Walker <anw@cuboid.co.uk> - 2020-10-29 14:41 +0000
                Re: Architectural design of a halting problem solution olcott <NoOne@NoWhere.com> - 2020-10-29 10:29 -0500
  Re: Architectural design of a halting problem solution Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-28 04:17 +0000
  Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 14:00 +0100
    Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2020-10-29 08:48 -0600
      Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-29 15:17 +0000
        Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) olcott <NoOne@NoWhere.com> - 2020-10-29 11:13 -0500
          Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-29 16:39 +0000
        Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Manfred <noname@add.invalid> - 2020-10-29 19:20 +0100
          Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-29 18:55 +0000
            Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) David Brown <david.brown@hesbynett.no> - 2020-10-30 11:02 +0100
              Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-30 10:52 +0000
                Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-10-30 19:47 +0000
              Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Ralf Goertz <me@myprovider.invalid> - 2020-10-30 12:55 +0100
              Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-30 16:33 +0000
  Re: Stop crossposting you imbecil spammer (Re: Architectural design of a halting problem solution Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 19:40 +0100

csiph-web