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


Groups > comp.theory > #25242

Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts)

Subject Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts)
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng
References (15 earlier) <1xxrH.532783$0W4.118610@fx42.iad> <9pOdnV6-_dGbOzPCnZ2dnUU7-InNnZ2d@giganews.com> <vTxrH.529688$RF4.144210@fx43.iad> <Z6CdnVHxBpjCLDPCnZ2dnUU7-ctQAAAA@giganews.com> <7KyrH.792482$eN2.539915@fx47.iad>
From olcott <NoOne@NoWhere.com>
Date 2020-11-13 11:22 -0600
Message-ID <G_6dnfRktulbXTPCnZ2dnUU7-Y2dnZ2d@giganews.com> (permalink)

Cross-posted to 3 groups.

Show all headers | View raw


On 11/13/2020 10:44 AM, Richard Damon wrote:
> On 11/13/20 11:16 AM, olcott wrote:
>> On 11/13/2020 9:46 AM, Richard Damon wrote:
>>> On 11/13/20 10:28 AM, olcott wrote:
>>>> On 11/13/2020 9:22 AM, Richard Damon wrote:
>>>>> On 11/13/20 8:48 AM, olcott wrote:
>>>>>> On 11/13/2020 5:17 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.
>>>>>>>
>>>>>>> And, in a separate point to André's, I encourage you to post this
>>>>>>> mantra
>>>>>>> every time you write about this topic because it makes it crystal
>>>>>>> clear
>>>>>>> that you are not talking about the halting problem.
>>>>>>>
>>>>>>> The correct return from H for the input <<P>, I> is true if P(I) is a
>>>>>>> finite computation and false otherwise.  That is the halting problem.
>>>>>>> P(I) is a finite computation even if it includes a call to H that
>>>>>>> "had
>>>>>>> to stop it".  P(I) is a finite computation even if that is the /only/
>>>>>>> reason for it being one.  P(I) is a finite computation if the
>>>>>>> execution
>>>>>>> is finite regardless of the reason or mechanism.
>>>>>>>
>>>>>>
>>>>>> Since it does divide all of its inputs into {halting and
>>>>>> not-halting} it
>>>>>> is a halt decider. That it does not use the defective criteria that
>>>>>> can
>>>>>> be fooled by an input that does the opposite of whatever the halt
>>>>>> decider decides makes the halting problem decidable.
>>>>>>
>>>>>
>>>>> ONLY if the division into Halting and non-halting is on the correct
>>>>> basis of it the original machine halted or not. Your 'decider'
>>>>> incorrectly determines that machines that will naturally halt, due to
>>>>> the required finite nature of H, will need to be aborted, and thus
>>>>> called non-halting, not due to infinite behavior of the machines, but
>>>>> due to limitations in your definition of H which can not handle many
>>>>> forms of recursive calls, which in the basic definition it needs to
>>>>> handle.
>>>>>
>>>>> Note, H is DEFINED as a Universal Turing Halting Decider which will
>>>>> decide if ANY Turing Machine (including Turing Machines which imbed
>>>>> copies of H in them) will ultimately Halt or be forever non-Halting,
>>>>> and
>>>>> that H will make that determination in finite time.
>>>>>
>>>>> Your version of H fails at this duty, and as such isn't a Halting
>>>>> Decider, or at least not a Correct Halting Decider (and if it isn't
>>>>> correct, it isn't really a decider). You could perhaps reframe your
>>>>> H as
>>>>> a partial halting decider, but then it isn't applicable to Linz.
>>>>>
>>>>> You also could frame you machine as an aborted decider, with an
>>>>> understanding that your definition of aborted is NOT the same as the
>>>>> definition of non-Halting, as you will decide to abort some machines
>>>>> that will halt. I also suspect that you machine will either not decide
>>>>> or decide incorrectly for some other machines.
>>>>>
>>>>
>>>> If a person decides that a black cat is black and this cat is black then
>>>> the person's decision is correct.
>>>>
>>>> If a UTM 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 decision on this input.
>>>>
>>>>
>>>
>>> Yes, you may have defined a 'My code needed to abort the execution of
>>> this program to stop it' decider, but that is not the same thing as a
>>> 'Halting' Decider, so has no bearing on theorems about halting.
>>
>> Since H does divide all of its inputs into {halting and not-halting}**
>> it is a halt decider.
>>
>>     **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
>>
>>
> 
> Except that it doesn't divide on Halting, it divides based on its own
> (incorrect) opinion of needing to abort, with a definition of aborting
> (because it is not based on actual need, but its own opinion of need)
> that differs from non-halting.
> 

// Linz H with some of the ⊢* states shown
08 bool H(u32 P, u32 I)  // Page 318
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 we remove line 15 all of the inputs that would have been decided to 
be not halting prove that they are indeed not halting by the fact that 
they fail to ever halt when line 15 is removed.


-- 
Copyright 2020 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

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 (V5) (new material added) olcott <NoOne@NoWhere.com> - 2020-11-11 08:45 -0600
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-11 15:23 +0000
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) olcott <NoOne@NoWhere.com> - 2020-11-11 09:26 -0600
  Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-11 17:29 +0000
    Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) olcott <NoOne@NoWhere.com> - 2020-11-11 17:13 -0600
      Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (new material added) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 01:06 +0000
        Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (tautology) olcott <NoOne@NoWhere.com> - 2020-11-11 19:20 -0600
          Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (tautology) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 02:08 +0000
            Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 00:09 -0600
              Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-12 08:06 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 09:19 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-12 10:40 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 12:21 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-12 12:09 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 22:46 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-13 01:22 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 07:55 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 07:57 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) André G. Isaak <agisaak@gm.invalid> - 2020-11-13 09:12 -0700
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 10:21 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 11:17 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 07:48 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 10:22 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 09:28 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 10:46 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 10:16 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-13 11:44 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-13 11:22 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-13 15:54 +0000
              Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-12 15:23 +0000
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 09:30 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-12 11:19 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 10:36 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Richard Damon <Richard@Damon-Family.org> - 2020-11-12 12:47 -0500
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-11-12 12:21 -0800
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 22:48 -0600
                Re: Refuting the halting problem proofs by deciding the previously undecidable input (V5) (verified facts) olcott <NoOne@NoWhere.com> - 2020-11-12 22:11 -0600

csiph-web