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


Groups > comp.theory > #28696

Re: Deciding the [would-not-halt] property

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Deciding the [would-not-halt] property
Date 2021-03-06 23:43 +0000
Organization A noiseless patient Spider
Message-ID <87mtvfdf0r.fsf@bsb.me.uk> (permalink)
References (8 earlier) <dc2dnWu2954a0N_9nZ2dnUU7-IXNnZ2d@giganews.com> <87k0qlh7ry.fsf@bsb.me.uk> <SqSdnT_tuJWX-d_9nZ2dnUU7-QOdnZ2d@giganews.com> <87r1ktfh5b.fsf@bsb.me.uk> <oc2dnTM49uvhAt_9nZ2dnUU7-TnNnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> The halt decider decides that if the input program was directly executed
> by a pure simulator that had no halt deciding capabilities that the
> input program would execute infinitely.

This is conventional halting, as everyone understands it, only phrased
in a silly way.  A halting program ("computation" would be better) is
one that does not halt.  There is no need to state this in terms of what
a simulation of it would do because, as you have quoted me 1,278 times,
a computation and it's (correct) simulation must have the same halting
status.

There is no algorithm to determine this property.

You have, in the past, been able to be clear about your new (and daft)
PO-halting, but this is not how to state it.  Go back to the code you
posted in response to my challenge last year.  That makes PO-halting
completely clear.

PO-halting is also impossible to determine (in general), but it does
work in the case you keep obsessing about, because you declare
"non-halting" to be the correct status to report for some halting
computations.  That'll do it every time!

-- 
Ben.

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


Thread

Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 08:51 -0600
  Re: Detecting infinite recursion (V2) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 10:55 -0500
    Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 10:04 -0600
      Re: Detecting infinite recursion (V2) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 11:17 -0500
        Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) olcott <NoOne@NoWhere.com> - 2021-03-04 10:29 -0600
          Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 11:44 -0500
            Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) olcott <NoOne@NoWhere.com> - 2021-03-04 11:12 -0600
              Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 13:17 -0500
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) olcott <NoOne@NoWhere.com> - 2021-03-04 12:27 -0600
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 14:08 -0500
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) olcott <NoOne@NoWhere.com> - 2021-03-04 13:17 -0600
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 14:43 -0500
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) olcott <NoOne@NoWhere.com> - 2021-03-04 14:09 -0600
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 15:58 -0500
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) olcott <NoOne@NoWhere.com> - 2021-03-04 13:31 -0600
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 14:47 -0500
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) olcott <NoOne@NoWhere.com> - 2021-03-04 14:10 -0600
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 16:04 -0500
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem)(no inconsistency) olcott <NoOne@NoWhere.com> - 2021-03-04 15:20 -0600
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem)(no inconsistency) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 17:34 -0500
                Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-04 19:40 +0000
          Re: Detecting infinite recursion (V2)(removing pathological self-reference from the halting problem) Peter <peterxpercival@hotmail.com> - 2021-03-04 16:55 +0000
  Re: Detecting infinite recursion (V2) David Brown <david.brown@hesbynett.no> - 2021-03-04 16:59 +0100
    Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 10:08 -0600
      Re: Detecting infinite recursion (V2) David Brown <david.brown@hesbynett.no> - 2021-03-04 17:39 +0100
        Re: Detecting infinite recursion (V2) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 11:58 -0500
        Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 11:22 -0600
    Re: Detecting infinite recursion (V2) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 11:24 -0500
  Re: Detecting infinite recursion (V2) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-03-04 19:21 +0000
    Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 13:38 -0600
      Re: Detecting infinite recursion (V2) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 14:49 -0500
        Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 14:12 -0600
          Re: Detecting infinite recursion (V2) Richard Damon <Richard@Damon-Family.org> - 2021-03-04 16:06 -0500
      Re: Detecting infinite recursion (V2) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2021-03-04 21:15 +0000
        Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 15:23 -0600
        Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 15:48 -0600
  Re: Detecting infinite recursion (V2) R Kym Horsell <kym@kymhorsell.com> - 2021-03-04 21:22 +0000
    Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 15:32 -0600
      Re: Detecting infinite recursion (V2) Alan Mackenzie <acm@muc.de> - 2021-03-04 22:54 +0000
        Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 17:31 -0600
          Re: Detecting infinite recursion (V2) Alan Mackenzie <acm@muc.de> - 2021-03-05 09:19 +0000
            Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-05 08:32 -0600
              Re: Detecting infinite recursion (V2) Alan Mackenzie <acm@muc.de> - 2021-03-05 14:53 +0000
                Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-05 09:26 -0600
                Re: Detecting infinite recursion (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-05 16:42 +0000
                Deciding the [would-not-halt] property olcott <NoOne@NoWhere.com> - 2021-03-05 11:02 -0600
                Re: Deciding the [would-not-halt] property Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-05 21:02 +0000
                Re: Deciding the [would-not-halt] property olcott <NoOne@NoWhere.com> - 2021-03-05 15:15 -0600
                Re: Deciding the [would-not-halt] property Richard Damon <Richard@Damon-Family.org> - 2021-03-05 20:42 -0500
                Re: Deciding the [would-not-halt] property Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-06 23:43 +0000
                Re: Deciding the [would-not-halt] property olcott <NoOne@NoWhere.com> - 2021-03-06 18:00 -0600
                Re: Deciding the [would-not-halt] property Richard Damon <Richard@Damon-Family.org> - 2021-03-06 19:33 -0500
                Re: Deciding the [would-not-halt] property Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-07 00:38 +0000
                Re: Deciding the [would-not-halt] property olcott <NoOne@NoWhere.com> - 2021-03-06 18:53 -0600
                Re: Deciding the [would-not-halt] property Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-07 01:15 +0000
                Re: Deciding the [would-not-halt] property olcott <NoOne@NoWhere.com> - 2021-03-06 19:26 -0600
                Re: Deciding the [would-not-halt] property Richard Damon <Richard@Damon-Family.org> - 2021-03-06 21:01 -0500
                Re: Deciding the [would-not-halt] property (Undecidability == error) olcott <NoOne@NoWhere.com> - 2021-03-06 20:08 -0600
                Re: Deciding the [would-not-halt] property (Undecidability == error) Richard Damon <Richard@Damon-Family.org> - 2021-03-06 22:00 -0500
                Re: Deciding the [would-not-halt] property (Undecidability == error) olcott <NoOne@NoWhere.com> - 2021-03-06 21:16 -0600
                Re: Deciding the [would-not-halt] property (Undecidability == error) Richard Damon <Richard@Damon-Family.org> - 2021-03-06 23:02 -0500
                Re: Deciding the [would-not-halt] property (Undecidability == error) olcott <NoOne@NoWhere.com> - 2021-03-06 22:17 -0600
                Re: Deciding the [would-not-halt] property (Undecidability == error) Richard Damon <Richard@Damon-Family.org> - 2021-03-07 09:30 -0500
                Re: Deciding the [would-not-halt] property (Undecidability == error) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-07 12:14 +0000
                Re: Deciding the [would-not-halt] property Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-07 12:06 +0000
                Re: Deciding the [would-not-halt] property Richard Damon <Richard@Damon-Family.org> - 2021-03-06 20:22 -0500
      Re: Detecting infinite recursion (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-05 00:15 +0000
        Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 18:26 -0600
          Re: Detecting infinite recursion (V2) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-03-05 01:25 +0000
            Re: Detecting infinite recursion (V2) olcott <NoOne@NoWhere.com> - 2021-03-04 19:40 -0600

csiph-web