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

Groups > comp.theory > #59416

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

Cross-posted to 2 groups.

Show all headers | View raw

On 11/7/2022 12:28 PM, Mr Flibble wrote:
> 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
> 

The halting problem itself is only the first paragraph below. The 
essence of the conventional proof that the halting problem cannot be 
solved is the second paragraph.

In computability theory, the halting problem is the problem of 
determining, from a description of an arbitrary computer program and an 
input, whether the program will finish running, or continue to run 
forever. Alan Turing proved in 1936 that a general algorithm to solve 
the halting problem for all possible program-input pairs cannot exist.

For any program H that might determine if programs halt, a 
"pathological" program D, called with some input, can pass its own 
source and its input to H and then specifically do the opposite of what 
H predicts D will do. No H can exist that handles this case. 
https://en.wikipedia.org/wiki/Halting_problem

-- 
Copyright 2022 Pete Olcott "Talent hits a target no one else can hit;
Genius hits a target no one else can see." Arthur Schopenhauer

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