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

Groups > comp.theory > #59400

Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract]

Show all headers | View raw

On Sat, 5 Nov 2022 21:54:16 -0400
Richard Damon <Richard@Damon-Family.org> wrote:

> On 11/5/22 9:13 PM, Mr Flibble wrote:
> > On Sat, 5 Nov 2022 17:05:35 -0500
> > olcott <polcott2@gmail.com> wrote:
> >   
> >> On 11/5/2022 4:57 PM, Mr Flibble wrote:  
> >>> On Sat, 5 Nov 2022 16:42:22 -0500
> >>> olcott <polcott2@gmail.com> wrote:
> >>>      
> >>>> On 11/5/2022 4:02 PM, Mr Flibble wrote:  
> >>>>> On Sat, 5 Nov 2022 13:10:54 -0500
> >>>>> olcott <polcott2@gmail.com> wrote:
> >>>>>         
> >>>>>> On 11/5/2022 12:05 PM, Mr Flibble wrote:  
> >>>>>>> On Sat, 5 Nov 2022 09:47:27 -0500
> >>>>>>> olcott <polcott2@gmail.com> wrote:
> >>>>>>>            
> >>>>>>>> The novel concept of a simulating halt decider enables C
> >>>>>>>> function H to correctly determine the halt status of C
> >>>>>>>> function D that implements the halting theorem's
> >>>>>>>> "impossible" input. When D is correctly simulated by H it
> >>>>>>>> remains stuck in recursive simulation until H aborts this
> >>>>>>>> simulation. D cannot do the opposite of the return value
> >>>>>>>> from H because this return value is unreachable by every
> >>>>>>>> simulated D. This same result is derived in Turing machine
> >>>>>>>> based proofs.
> >>>>>>>>
> >>>>>>>> On 11/4/2022 9:33 AM, olcott wrote:  
> >>>>>>>>> Can you see that simulating halt decider H correctly
> >>>>>>>>> determines the halt status of the halting problem's
> >>>>>>>>> "impossible" input D?
> >>>>>>>>>
> >>>>>>>>> void D(void (*x)())
> >>>>>>>>> {
> >>>>>>>>>        int Halt_Status = H(x, x);
> >>>>>>>>>        if (Halt_Status)
> >>>>>>>>>          HERE: goto HERE;
> >>>>>>>>>        return;
> >>>>>>>>> }
> >>>>>>>>>
> >>>>>>>>> int main()
> >>>>>>>>> {
> >>>>>>>>>        Output("Input_Halts = ", H(D, D));
> >>>>>>>>> }
> >>>>>>>>>
> >>>>>>>>> https://www.researchgate.net/publication/364657019_Simulating_Halt_Decider_Applied_to_the_Halting_Theorem
> >>>>>>>>>               
> >>>>>>>>           
> >>>>>>>
> >>>>>>> As I said before it is sufficient to detect nested simulation
> >>>>>>> to assert the presence of a category error; trying to map
> >>>>>>> that to a valid halting decision of non-halting muddies the
> >>>>>>> water and implies no such category error exists which is
> >>>>>>> wrong: nested simulation PREVENTS a halting decision being
> >>>>>>> made because of the category error present in [Strachey 1965]
> >>>>>>> and the proofs predicated on it. Again: you don't have to
> >>>>>>> abort simulation or give an artificial halting decision of
> >>>>>>> non-halting to refute the halting problem proofs, the simple
> >>>>>>> presence of the category error does that.
> >>>>>>>
> >>>>>>> /Flibble
> >>>>>>>            
> >>>>>>
> >>>>>> Unlike with Gödel's incompleteness theorem and the Tarski
> >>>>>> undefinability theorem with mathematical formulas that can only
> >>>>>> just sit on the page, TM's have intelligence and can take
> >>>>>> corrective action for what would otherwise simply be a category
> >>>>>> error.  
> >>>>>
> >>>>> There is no corrective action for a category error; the category
> >>>>> error can be used to directly refute the halting problem proofs
> >>>>> without recourse to creating an actual simulating halt decider
> >>>>> that gives an artificial result of non-halting.
> >>>>>
> >>>>> /Flibble
> >>>>>
> >>>>>         
> >>>>
> >>>> It is not an artificial result.  
> >>>    
> >>> It is an artificial result because the category error means the
> >>> input is INVALID; a halt decider shouldn't be able to give a
> >>> traditional decision result for INVALID input.
> >>>
> >>> /Flibble  
> >>
> >> Your assumption of category error is correct for non simulating
> >> halt deciders. In this case the input would contradict any value
> >> that its decider returns.  
> > 
> > The category error is not due to the contradiction, the category
> > error is due to the input referencing the decider.  
> 
> Why is that a "Category Error"?
> 
> Is not a computation allowed to use other Computations as parts of it?
> 
> What makes THAT one not allowed?
> 
> Or is the problem that the decider isn't actually a Computation of
> the required class?
> 
> I agree, it can't be defined to use what ever decider we happen to be 
> using at the moment (since that isn't an input to the computation),
> but what is wrong with saying we want to use this particular decider
> that happens to be making the claim to be able to decide on ALL
> programs. (Which is the H in the proof).

Proof of the existence of the category error is the fact that if the
halt decider is of the simulating type we get an infinitely nested
simulation or recursion.

/Flibble

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

Thread

Simulating Halt Decider Applied to the Halting Theorem olcott <polcott2@gmail.com> - 2022-11-04 09:33 -0500
  Re: Simulating Halt Decider Applied to the Halting Theorem Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-04 15:09 +0000
    Re: Simulating Halt Decider Applied to the Halting Theorem olcott <polcott2@gmail.com> - 2022-11-04 10:28 -0500
  Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] olcott <polcott2@gmail.com> - 2022-11-05 09:47 -0500
    Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-05 17:05 +0000
      Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] olcott <polcott2@gmail.com> - 2022-11-05 13:10 -0500
        Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-05 21:02 +0000
          Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] olcott <polcott2@gmail.com> - 2022-11-05 16:42 -0500
            Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-05 21:57 +0000
              Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] olcott <polcott2@gmail.com> - 2022-11-05 17:05 -0500
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-06 01:13 +0000
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Richard Damon <Richard@Damon-Family.org> - 2022-11-05 21:54 -0400
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-06 14:09 +0000
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Richard Damon <Richard@Damon-Family.org> - 2022-11-06 09:34 -0500
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-06 23:09 +0000
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Richard Damon <Richard@Damon-Family.org> - 2022-11-06 18:24 -0500
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Mr Flibble <flibble@reddwarf.jmc.corp> - 2022-11-07 18:28 +0000
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] olcott <polcott2@gmail.com> - 2022-11-07 13:03 -0600
                Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] olcott <polcott2@gmail.com> - 2022-11-06 08:40 -0600
        Re: Simulating Halt Decider Applied to the Halting Theorem [new abstract] Richard Damon <Richard@Damon-Family.org> - 2022-11-05 17:06 -0400

csiph-web