Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Ben Bacarisse <ben@bsb.me.uk>
Newsgroups: comp.theory
Subject: Re: Halting Problem Corrected
Date: Sat, 17 May 2025 13:14:01 +0100
Organization: A noiseless patient Spider
Lines: 28
Message-ID: <87jz6f1lkm.fsf@bsb.me.uk>
References: <hVZVP.1247810$4AM6.1119925@fx17.ams4>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Sat, 17 May 2025 14:14:02 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="e5f9c87a41e234385ac543eb8f6a5fac";
	logging-data="415109"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+fpllVPFeshubr5P8eBaiddWms4RMb9Dg="
User-Agent: Gnus/5.13 (Gnus v5.13)
Cancel-Lock: sha1:qjkmQ1hNqBAzX5SY4walTFluywc=
	sha1:rhjfXq3jVRr7rmQ1LgAnTRWou1w=
X-BSB-Auth: 1.5c0108e7a45ec09fbc5d.20250517131401BST.87jz6f1lkm.fsf@bsb.me.uk

Mr Flibble <flibble@red-dwarf.jmc.corp> writes:

> Obviously my idea necessitates extending the definition of a halt
> decider:
>
> 1) Decider decision is HALTS if input halts.
> 2) Decider decision is NON-HALTING if input does not halt.
> 3) Decider rejects pathological input as invalid by signaling sNaP.
>
> Thoughts?

The trouble is that this specification has a pointless third case.
Since every "input" either halts or does not halt, all inputs are
covered by your first two cases.  There are no computations that don't
do one or the other.

You can certainly have an almost-decider, AHD, that detects three cases:

1) The computations AHD can definitely work out are halting;
2) the computations AHD can definitely work our are non-halting;
3) all the others.

But that's old news.  Of course such an AHD could well be very useful
depending on how good it is, but it's not of any interest from a
theoretical point of view.

-- 
Ben.