Re: Getting Around the Halting Problem

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> (permalink)
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

Show key headers only | View raw

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?

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

Thread

Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-19 19:32 -0700
  Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-20 02:42 +0000
  Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-20 04:01 +0100
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-19 22:26 -0700
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-19 22:28 -0700
      Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-20 12:56 +0100
  Re: Getting Around the Halting Problem olcott <NoOne@NoWhere.com> - 2020-08-19 22:04 -0500
  Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-20 17:07 +0000
    Re: Getting Around the Halting Problem (abstract versus concrete) olcott <NoOne@NoWhere.com> - 2020-08-20 12:35 -0500
  Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-20 17:34 +0000
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-20 12:08 -0700
      Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-20 20:18 +0100
      Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-20 19:18 +0000
        Re: Getting Around the Halting Problem olcott <NoOne@NoWhere.com> - 2020-08-20 14:30 -0500
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-20 12:46 -0700
        Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-20 23:54 +0000
      Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-20 23:43 +0000
      Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-21 17:10 +0000
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-21 18:12 -0700
          Re: Getting Around the Halting Problem Jeff Barnett <jbb@notatt.com> - 2020-08-21 22:24 -0600
            Re: Getting Around the Halting Problem olcott <NoOne@NoWhere.com> - 2020-08-22 00:29 -0500
            Re: Getting Around the Halting Problem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-22 11:14 +0100
              Re: Getting Around the Halting Problem Jeff Barnett <jbb@notatt.com> - 2020-08-22 12:05 -0600
    Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-23 10:15 -0700
      Re: Getting Around the Halting Problem Peter <peterxpercival@hotmail.com> - 2020-08-23 18:26 +0100
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-23 11:29 -0700
      Re: Getting Around the Halting Problem Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-24 01:06 +0000
        Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-23 21:26 -0700
  Re: Getting Around the Halting Problem Newberry <newberryxy@gmail.com> - 2020-08-22 20:39 -0700
    Re: Getting Around the Halting Problem R Kym Horsell <kym@kymhorsell.com> - 2020-08-23 07:44 +0000

csiph-web