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

Groups > comp.theory > #59415

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

Show all headers | View raw

On Sun, 6 Nov 2022 18:24:43 -0500
Richard Damon <Richard@Damon-Family.org> wrote:

> On 11/6/22 6:09 PM, Mr Flibble wrote:
> > 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
> >   
> 
> What is the category error?
> 
> A given machine with a given input will either halt or not. No
> problem with that question.
> 
> The decider needs to be a Turing Machine that gives the answer about 
> whether the Turing Machine given (via a representation) when given
> the specified input will Halt or Not.
> 
> If the claimed decider is a Turing Machine, then so will the H^
> machine be one, and its representation can be made.
> 
> For any given decider, there IS a definite answer to the question (it 
> might not match what the decider gives) for ANY possible input, thus
> for this one.
> 
> The fact that the decider can't give the right answer is NOT a
> category error, but an indication that the problem is just not
> Computable, which is an ALLOWED result. Not all functions are
> computable.

The category error is unrelated to the contradiction: the category
error is the self reference in the problem definition.

> 
> Your category error is in the idea that you can make a Halt Decider 
> based on just simulating and that the simulation will define the
> Halting Property of the input. It is NOT with the definition of the
> Halting Problem, but with the proposed solution.

I have withdrawn for consideration by signaling simulating halt decider
because it sneakily tries to get around the category error which is the
wrong approach.

> 
> A Simulationg Halting Decider that gets caught is an infinite
> simulation loop just fails to be a decider, and one that aborts fails
> to have a simulation that proves non-halting, it just prove doesn't
> halt in a spedified finite time, but might halt in a longer time.
> 
> Note, there is NO "Self Reference" in the Turing Machines, because 
> Turing Machine don't "Reference" things. This is why the problem says 
> that H^ starts with a COPY of H, because it has no way to "reference"
> H to use it.

The self reference is in the problem definition itself.

/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