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

Groups > comp.theory > #59407

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

Show all headers | View raw

On Sun, 6 Nov 2022 09:34:22 -0500
Richard Damon <Richard@Damon-Family.org> wrote:

> On 11/6/22 9:09 AM, Mr Flibble wrote:
> > 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
> >   
> 
> Which is a problem in the Halt Decider, not the program under test.
> The DECIDER has the requirement of finite processing, not the program
> under test.
> 
> What error was made in the construction of the program under test
> that makes it not a valid program.
> 
> You must have a very weak model of computation if you call a
> sub-program that is DEFINED to always return an answer and have to
> worry that sometimes it doesn't.
> 
> The problem is that a claim for ALL programs/Turing Machines must
> mean ALL.
> 
> If The decider is a Turing Machine, so must this test program,
> because its construction from the Decider is fully described.
> 
> If the test program is not a valid program, what that proves is that
> the decider wasn't a valid program either.
> 
> You need to either show what error was made in forming H^ from H,
> that makes H^ not a Turing Machine when H was, or admit that H wasn't
> a Turing Machine, or doesn't actually meet its requirements.

The category error (infinite self reference) is a property of the
Halting Problem as defined rather than a property of the specific type
of halting decider used.

/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