Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Mikko <mikko.levanto@iki.fi>
Newsgroups: comp.theory
Subject: Re: Defining a correct halt decider
Date: Mon, 5 Aug 2024 11:08:24 +0300
Organization: -
Lines: 35
Message-ID: <v8q19o$iqvb$1@dont-email.me>
References: <v8o47a$3ml4$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 05 Aug 2024 10:08:24 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="bbfb59f828059e193a33ed558dfca0d5";
	logging-data="617451"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/lJYTijblNTXjodlv7T7rl"
User-Agent: Unison/2.2
Cancel-Lock: sha1:nHGn5AbNDlIlyT3cDMnKGLiinYQ=
Bytes: 1865

On 2024-08-04 14:46:02 +0000, olcott said:

> When we define an input that does the opposite of whatever
> value that its halt decider reports there is a way for the
> halt decider to report correctly.
> 
> int DD()
> {
>    int Halt_Status = HHH(DD);
>    if (Halt_Status)
>      HERE: goto HERE;
>    return Halt_Status;
> }
> 
> int main()
> {
>    HHH(DD);
> }
> 
> HHH returns false indicating that it cannot
> correctly determine that its input halts.
> True would mean that its input halts.

That is called a "partial halt decider". The set of requirements is
a subset of the requirements for "halt decider" but still require
that the answer is not "halts" if the input does not halt and that
the answer is not "does not halt" if the input halts. The difference
is that a "halt decider" is required to give one of these answers
for every input but a "partial halt decider" is not.

For every computation there is a partial halt decider that answers it.

-- 
Mikko