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


Groups > comp.theory > #25141

Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4)

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4)
Date 2020-11-11 20:14 +0000
Organization A noiseless patient Spider
Message-ID <87361fvef2.fsf@bsb.me.uk> (permalink)
References <p8-dnR1l3oGjsDbCnZ2dnUU7-SXNnZ2d@giganews.com> <877dqswu19.fsf@bsb.me.uk> <poSdndbjB9An2zbCnZ2dnUU7-WXNnZ2d@giganews.com> <87pn4jvrhd.fsf@bsb.me.uk> <nPKdnXp65oCqmDHCnZ2dnUU7-InNnZ2d@giganews.com>

Show all headers | View raw


olcott <NoOne@NoWhere.com> writes:

> On 11/11/2020 9:32 AM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 11/10/2020 7:40 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> 01 void H_Hat(u32 P)
>>>>> 02 {
>>>>> 03   if (H(P, P))
>>>>> 04     HERE: goto HERE;
>>>>> 05   else
>>>>> 06     HALT
>>>>> 07 }
>>>>>
>>>>> 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 }
>>>>>
>>>>> When-so-ever a halt decider correctly determines that its input would
>>>>> never halt unless forced to halt by this halt decider this halt
>>>>> decider has made a correct not-halting determination.
>>>>
>>>> No.  The correct answer as to the halting of the computation
>>>> H_Hat(H_Hat) is based on whether H_Hat(H_Hat) is or is not a halting
>>>> computation.  There is no subjunctive here.  It is or it is not a finite
>>>> computation.  What it /would/ do, under some other circumstance, is
>>>> irrelevant.
>>>
>>> Intuitively it may seem that way yet an actual decider is only
>>> correctly judged on the basis of how it decides its inputs.
>>
>> We are in agreement -- the only way to judge a decider is on the answer
>> given for each input.  In the case if (H_Hat, H_Hat), H gives the answer
>> false.  This is the wrong answer for a halting computation.
>
> The decision of every decider can only be correctly measured against
> its input.

A rather obvious point and one never in dispute.

> The question is did the decider meet its own criterion measure for its
> input?

I agree that that appears to be your question.  Another question is
whether the decider meets the specified criteria.

In this case, the specified criterion is whether the input represents a
finite computation.  You function H gets the answer wrong according to
this measure.  Other measures are available.  None are relevant to the
halting problem.

You have shown yourself to stubborn and deeply confused in the past, but
I really don't think you can't see that whether the given computation
halts is what matters in the halting problem.  Whether a computation
halts only because the decider had to step in and stop it makes no
difference.  It's still a halting computation, and H should return true
when given those arguments.

This linkage between the decider and the computations it has to decide
is unavoidable, and is why the proof sketched in Linz always works, no
matter what the computational model is.

I urge to to read "Gödel, Escher, Bach: an Eternal Golden Braid".  In
particular, the dialogue about making an unplayable record.  It has no
maths in it.

-- 
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 (V4) olcott <NoOne@NoWhere.com> - 2020-11-10 18:15 -0600
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-10 16:30 -0800
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) olcott <NoOne@NoWhere.com> - 2020-11-10 18:56 -0600
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 01:40 +0000
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) olcott <NoOne@NoWhere.com> - 2020-11-10 20:04 -0600
      Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 15:32 +0000
        Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) olcott <NoOne@NoWhere.com> - 2020-11-11 09:37 -0600
          Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 20:14 +0000
        Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-11 08:00 -0800
          Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) olcott <NoOne@NoWhere.com> - 2020-11-11 10:04 -0600
          Re: Refuting the halting problem proofs by deciding the previously undecidable input (V4) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 17:21 +0000

csiph-web