Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #25273

Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ]

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ]
Date 2020-11-14 14:54 +0000
Organization A noiseless patient Spider
Message-ID <87blg0m1jc.fsf@bsb.me.uk> (permalink)
References (6 earlier) <oa6dncC29b13UDPCnZ2dnUU7-cnNnZ2d@giganews.com> <87v9e8nb1v.fsf@bsb.me.uk> <UKKdnZM2Yp8dkTLCnZ2dnUU7-X_NnZ2d@giganews.com> <87mtzkn1xr.fsf@bsb.me.uk> <5f6dnU35XvQ68zLCnZ2dnUU7-a_NnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> On 11/13/2020 7:48 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 11/13/2020 4:31 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> On 11/13/2020 11:56 AM, Ben Bacarisse wrote:
>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>
>>>>>>> On 11/13/2020 10:24 AM, Richard Damon wrote:
>>>>>>>> On 11/13/20 11:09 AM, olcott wrote:
>>>>>>>>> On 11/13/2020 9:51 AM, Ben Bacarisse wrote:
>>>>>>>>>> olcott <NoOne@NoWhere.com> writes:
>>>>>>>>>>
>>>>>>>>>>> When-so-ever UTM halt decider H decides that:
>>>>>>>>>>> (1) its input (<P>,I) would never halt unless H stopped simulating it
>>>>>>>>>>>         and
>>>>>>>>>>> (2) its input (<P>,I) would never halt unless H stopped simulating it
>>>>>>>>>>> then H has made a correct not-halting decision on this input.
>>>>>>>>>>>
>>>>>>>>>>> Since it does divide all of its inputs into {halting and
>>>>>>>>>>> not-halting}** it is a halt decider.
>>>>>>>>>>
>>>>>>>>>> No, that's not what the halting problem is about.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Sure it is:
>>>>>>>>>
>>>>>>>>>        **The Halting problem is a problem in computer science.
>>>>>>>>>        The problem is looking at a computer program and finding
>>>>>>>>>        out if the program is going to run forever or not. We say
>>>>>>>>>        that a program "solves the halting problem" if it can
>>>>>>>>>        look at any other program and tell if that other program
>>>>>>>>>        will run forever or not.
>>>>>>>>>        https://simple.wikipedia.org/wiki/Halting_problem
>>>>>>>>>
>>>>>>>>> Glancing at a few of my words for the purpose of contriving some sort of
>>>>>>>>> rebuttal has not ultimately been a very effective strategy for you.
>>>>>>>>>
>>>>>>>>
>>>>>>>> The key differencne between that and what you say is that this
>>>>>>>> definition is based on the ACTUAL behavior of the actual program, and
>>>>>>>> not on what some program did or did not do while analyising the program.
>>>>>>>>
>>>>>>>> YOUR definition focuses on what the decider did, not what the program
>>>>>>>> under test does, and if there is a possible difference, you resolve it
>>>>>>>> by focusing on the decider, and NOT on the actual program. Thus, you
>>>>>>>> program is NOT a true Halting Decider.
>>>>>>>>
>>>>>>>
>>>>>>> Since H does divide all of its inputs into {halting and not-halting}
>>>>>>> it is a halt decider.
>>>>>>
>>>>>> It does not, as you yourself have told us.  Given
>>>>>>
>>>>>> void H_Hat(u32 P) { if (H(P, P)) while (1); }
>>>>>>
>>>>>>> 08 bool H(u32 P, u32 I)
>>>>>>> 09 {
>>>>>>> 10   bool Halted  = false;
>>>>>>> 11   bool Aborted = false;
>>>>>>> 12   while (!Halted && !Aborted)
>>>>>>> 13   {
>>>>>>> 14     Halted  = DebugStep(P, I);
>>>>>>> 15     Aborted = Needs_To_Be_Aborted();
>>>>>>> 16   }
>>>>>>> 17   return !Aborted;
>>>>>>> 18 }
>>>>>>
>>>>>> You have confirmed that H(H_Hat, H_Hat) is false and that H_Hat(H_hat)
>>>>>> is a finite computation.
<cut>
> This is NOT a valid counter-example proving that a decider decides its
> inputs incorrectly:
>
> int main()
>   H_Hat(H_Hat);
>
> Because every counter-example proving that a decider decides its
> inputs incorrectly must itself be an input to this decider that this
> decider decides incorrectly.

As is the case here: H(H_Hat, H_Hat) incorrectly reports that
H_Hat(H_hat) is not a finite computation.

> Can you come up with an actual counter-example?

You provided it, originally.  I wrote H_Hat above just because you had
not included it.  You simply can't accept that the halting problem is
about the code as written.  You have confirmed that H(H_Hat, H_Hat) is
false and that H_Hat(H_hat) is a finite computation.  That's the wrong
answer.  I am happy to repeat this every time you try to pretend you
don't know this.

-- 
Ben.

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


Thread

Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 09:14 -0600
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 15:51 +0000
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 10:09 -0600
      Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 11:24 -0500
        Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 10:37 -0600
          Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 17:56 +0000
            Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 12:18 -0600
              Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 22:31 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 16:45 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 17:56 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 17:02 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 18:59 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 18:21 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 20:54 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 20:35 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 22:39 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] olcott <NoOne@NoWhere.com> - 2020-11-13 22:11 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] olcott <NoOne@NoWhere.com> - 2020-11-13 22:22 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] Richard Damon <Richard@Damon-Family.org> - 2020-11-14 09:33 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 01:48 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 20:24 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 15:09 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] olcott <NoOne@NoWhere.com> - 2020-11-13 23:44 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) [ counter-example? ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 14:54 +0000
      Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 17:39 +0000
        Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 12:14 -0600
          Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 22:12 +0000
            Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 16:32 -0600
              Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 01:56 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) olcott <NoOne@NoWhere.com> - 2020-11-13 21:23 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-14 14:54 +0000
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Jeff Barnett <jbb@notatt.com> - 2020-11-13 11:34 -0700
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-13 20:45 +0000
      Re: Refuting the halting problem proofs by deciding the previously undecidable input (V7) Jeff Barnett <jbb@notatt.com> - 2020-11-13 14:18 -0700

csiph-web