Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail
From: Newberry <newberryxy@gmail.com>
Newsgroups: comp.theory
Subject: Re: Getting Around the Halting Problem
Date: Wed, 19 Aug 2020 22:26:18 -0700
Organization: A noiseless patient Spider
Lines: 48
Message-ID: <5F3E097A.6000903@gmail.com>
References: <rhknbg$ctc$1@dont-email.me> <87blj681hp.fsf@bsb.me.uk>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: reader02.eternal-september.org; posting-host="6de15d2f72d0be87130a307e4bdf027c"; logging-data="20608"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/irDwBSHPQ4z+9TbUqBY6gAgodbhsjo1U="
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:27.0) Gecko/20100101 Firefox/27.0 SeaMonkey/2.24
Cancel-Lock: sha1:gNqVUM0wrWp78GzHI55wCRJJCYg=
In-Reply-To: <87blj681hp.fsf@bsb.me.uk>
Xref: csiph.com comp.theory:22478

Ben Bacarisse wrote:
> Newberry <newberryxy@gmail.com> writes:
>
>> Let H(P, n) be a program
>
> I'd say that H is a program and H(P, n) is a computation.
>
>> with two possible outcomes: TRUE and FALSE.
>
> and presumably /only/ two outcomes.  And H always halts?
>
>> The parameter P is a program and n is its input. Suppose that H(P, n)
>> = TRUE if and only if P halts on n. Suppose further that if H(P, n) =
>> FALSE then P does not halt on n, and suppose that H is sound.
>
> What does sound mean in this context?
>
>> Let
>> furthermore P* be a program with itself as a parameter. The claim is
>> that there exists a program H such that H(H, H*) = FALSE,
>
> Is this H related to the H above?  In other words are you claiming an H
> with all these properties:
>
>    For all x: H(x) always halts yielding either TRUE or FALSE.
>    For all P, x: H(P, x) = FALSE iff P(x) does not halt.
>    Exists x: H(H, x) = FALSE
>
> ?  If so, that seems like an obvious contradiction, regardless of the *
> notation.
>
> I'm guessing a bit because you have not introduced any notion of
> encoding of either programs or inputs.  In particular, that all programs
> have only one argument and the P(a, b) is just P provided with a single
> argument pair.
>
>> that is, H
>> proves that it does not prove that H* halts.
>>
>> https://www.researchgate.net/publication/316562253_Getting_around_the_Halting_Problem
>

"And H always halts?"
"If so, that seems like an obvious contradiction"

Does that answer your question?