Re: HP undecidability is not an axiom

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups	comp.theory
Subject	Re: HP undecidability is not an axiom
Date	2021-07-17 00:11 +0100
Organization	A noiseless patient Spider
Message-ID	<87y2a5onur.fsf@bsb.me.uk> (permalink)
References	<20210716223332.000031bf@reddwarf.jmc> <87fswdq4rf.fsf@bsb.me.uk> <sct2b6$lrr$1@dont-email.me>

Show all headers | View raw

Jeff Barnett <jbb@notatt.com> writes:

> On 7/16/2021 4:21 PM, Ben Bacarisse wrote:
>> Mr Flibble <flibble@reddwarf.jmc> writes:
>> 
>>> The halting problem being undecidable is NOT a fucking axiom;
>> Agreed.  It follows logically from most reasonable sets of axioms.
>> Interestingly, halting being decidable /can/ be taken as an axiom
>> without introducing any inconsistency.
>
> In what base system or systems is the above true? I'm thinking "in the
> sense" that Godel follows in systems that allow sufficient arithmetic.
> I'm not sure I'm asking this question in the best way; if not, please
> help me out.

And I'm sure I'm not putting correctly.  What I mean is that the theory
of halting-oracle TMs is consistent.  Of course, it has it's own halting
theorem: halting-oracle TM halting is not decidable by any
halting-oracle TM and there's an infinite chain of such theories.

-- 
Ben.

Thread

HP undecidability is not an axiom Mr Flibble <flibble@reddwarf.jmc> - 2021-07-16 22:33 +0100
  Re: HP undecidability is not an axiom olcott <NoOne@NoWhere.com> - 2021-07-16 17:02 -0500
  Re: HP undecidability is not an axiom Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-16 23:21 +0100
    Re: HP undecidability is not an axiom Jeff Barnett <jbb@notatt.com> - 2021-07-16 16:48 -0600
      Re: HP undecidability is not an axiom Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 00:11 +0100
        Re: HP undecidability is not an axiom Jeff Barnett <jbb@notatt.com> - 2021-07-16 23:07 -0600
          Re: HP undecidability is not an axiom Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-07-17 21:15 +0100
            Re: HP undecidability is not an axiom Jeff Barnett <jbb@notatt.com> - 2021-07-17 17:30 -0600
  Re: HP undecidability is not an axiom Alan Mackenzie <acm@muc.de> - 2021-07-17 12:00 +0000
    Re: HP undecidability is not an axiom Mr Flibble <flibble@reddwarf.jmc> - 2021-07-17 13:03 +0100
      Re: HP undecidability is not an axiom Alan Mackenzie <acm@muc.de> - 2021-07-17 12:30 +0000

csiph-web