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


Groups > comp.theory > #24703

Re: SOLUTION TO THE HALTING PROBLEM!

Subject Re: SOLUTION TO THE HALTING PROBLEM!
Newsgroups comp.theory
References (12 earlier) <_G_mH.766667$AN2.730575@fx46.iad> <VP-dndHkLJb3EQHCnZ2dnUU7-SHNnZ2d@giganews.com> <BG0nH.97951$Ml5.89653@fx24.iad> <8bOdnWNsDbi_NAHCnZ2dnUU7-RHNnZ2d@giganews.com> <5a2b4415-169f-4664-ab94-f3859027daeen@googlegroups.com>
From olcott <NoOne@NoWhere.com>
Date 2020-10-30 19:14 -0500
Message-ID <tuadnZJJ9uzXMQHCnZ2dnUU7-InNnZ2d@giganews.com> (permalink)

Show all headers | View raw


On 10/30/2020 7:07 PM, Graham Cooper wrote:
> On Saturday, October 31, 2020 at 10:00:41 AM UTC+10, olcott wrote:
>> On 10/30/2020 5:43 PM, Richard Damon wrote:
>>> On 10/30/20 5:58 PM, olcott wrote:
>>>> On 10/30/2020 3:27 PM, Richard Damon wrote:
>>>
>>>>> Please read and tell me where I am off.
>>>>>
>>>>> So, we start with the question does a Machine M with input N halt or
>>>>> not. This IS the original question we want the answer to, RIGHT?
>>>>
>>>> Yes.
>>>>
>>>>> We presume that we can make a Turing Machine H, that is supposedly able
>>>>> to answer the question. The stated requirements are that H will, being
>>>>> given a representation for machine M with input N, will in a finite
>>>>> amount of time, end up in one of two states, dependent on the answer to
>>>>> the above question. RIGHT?
>>>>
>>>> Yes.
>>>>
>>>>> We have a machine, H_Hat2, which by simple inspection, WILL halt,
>>>>
>>>> No. If you want to make a machine that definitely halts you can do
>>>> something like this:
>>>
>>> We KNOW H must halt, because it is defined to do so. Where is there
>>> possible non-halting behavior, GIVEN that H is defined to work in finite
>>> time. If H has a problem in working in finite time, it says that H
>>> doesn't meet its requirements.
>>>
>>>>
>>>> u32 Add(u32 X, u32 Y)
>>>> {
>>>> u32 Z = X + Y;
>>>> return Z;
>>>> }
>>>
>>> and the function
>>>
>>> u32 testFun(u32 X, u32 Y)
>>> {
>>> doSomethingFinite();
>>> return 0;
>>> }
>>>
>>> will also be sure to halt, if we know that doSomethingFinite() is going
>>> to return in finite time.
>>>
>>>>
>>>>> the
>>>>> only way it can't halt is if H doesn't met its requirements. RIGHT?
>>>>
>>>> The only way it can halt is that:
>>>> bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat2, H_Hat2)
>>>> aborted the first instance of H_Hat2.
>>>
>>>
>>> THERE IS NO REQUIREMENT THAT H EVEN HAVE such a function.
>>>
>>> One conceivable method is H detects that the machine is recursively
>>> calling H, and then sees what happens in the two cases. If either of
>>> them agrees with that trial, then that is the answer. One then needs to
>>> decide how to handle the 'trick' case of Linz's H_Hat, but that is a
>>> different issue. Note, you should only be able to try this out if it
>>> really is the case that the machine is being contrary.
>>>
>>> You still have the problem of detecting non-Halting behavior in the
>>> unbounded non-halting machine, but this program (nor H_Hat) exihibits
>>> that problem.
>>>
>>>>
>>>>>  From this, the answer to the original question, is clearly HALTS. RIGHT?
>>>>>
>>>>
>>>> void H_Hat2(u32 P)
>>>> {
>>>> if (Aborted_Because_Non_Halting_Behavior_Detected(P, P))
>>>> MOV_EAX_1 // Execution of P(P) has been aborted
>>>> else
>>>> {
>>>> MOV_EAX_0 // P(P) has halted
>>>> HERE: goto HERE;
>>>> }
>>>> HALT
>>>> }
>>>>
>>>> When P = H_Hat2, then this line specifies:
>>>> if (Aborted_Because_Non_Halting_Behavior_Detected(H_Hat2, H_Hat2))
>>>> which is is infinite recursion unless the above function aborts its
>>>> execution trace of H_Hat2.
>>>>
>>>> H_Hat2 only halts because it is forced to halt.
>>>>
>>>>> You are arguing, that because of how you implemented H, it is ok for it
>>>>> to give a different answer, that it had to abort the machine because H
>>>>> couldn't see pass the recursion. RIGHT?
>>>>
>>>> No. Not at all. Not in the least. There is no seeing past the recursion.
>>>
>>> YES THERE IS, see above.
>>>
>>>>
>>>> Either this function aborts the recursion:
>>>> bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat2, H_Hat2)
>>>> or the recursion never ceases.
>>>
>>> The mere idea that emulation is THE solution is wrong.
>>>>
>>>>> Thus, by you, the answer to a question about M(N) is at least as much a
>>>>> function of the machine H that is answering it. RIGHT?
>>>>
>>>> In every conventional halting problem proof counter-example the halting
>>>> decider's decision is the basis for the input program's behavior. This
>>>> is the key thing that has previously been construed as making the
>>>> halting problem undecidable.
>>>>
>>>> Once we break this cause-and-effect chain and only make the halting
>>>> decision upon the termination of the input the halting problem can no
>>>> longer be shown to be undecidable.
>>>
>>> While I will admit that this is getting out of my area of expertise, I
>>> do know that there are a number of different proofs that show that there
>>> can not be a universal halting decider. In part becaue the existence of
>>> a truely universal halt decider would make some things that have been
>>> shown to be uncomputable would then have a method to compute them in
>>> finite time.
>>>
>>>>
>>>>> This last part seems strange, that the question about a Turing Machine
>>>>> isn't just about the machine, but about the tool used to measure that
>>>>> machine. RIGHT?
>>>>
>>>> Once the input program's behavior is not allowed to be effected by the halt
>>>> decider's decision the halting problem becomes decidable.
>>>
>>> The data input was never in control of the halt decider. It is only a
>>> flaw in the Halt decider if the input makes the halt decider misbehave.
>>>
>>> The decider's job is to figure out what the input would do, but it is
>>> always in control.
>>>>
>>>>> The purpose of the Halting Machine, isn't just to get 'an answer' but to
>>>>> get information about the true behavior of a machine. Your modification
>>>>> destroys that information.
>>>>
>>>> No, not at all, not in the least little bit.
>>>> The rest of what you say strays from the key prerequistite point.
>>>>
>>>> Until you fully understand how and why this is decided correctly:
>>>> bool Aborted_Because_Non_Halting_Behavior_Detected(H_Hat2, H_Hat2)
>>>> You have gaps in your reasoning that need to be filled.
>>>
>>> So you DO think that how the halting decider works is more important
>>> than the problem that it was put on??
>>>
>>> Does that mean that there is more than one right answer to the question
>>> does M(N) halt?
>>>
>> It looks like I have to backup to the gist of the idea.
>> The conventional idea of a halt decider can be fooled by simply making
>> the input program do the opposite of whatever the halt decider decides.
>>
>> When the halt decider only makes its decision after the input program
>> has stopped running it cannot possibly do the opposite of whatever the
>> halt decider decides.
>>
>> This simple little change makes the halting problem decidable.
> 
> A/  HALT(prog,inp) doesnt RUN prog(inp)

If the goal it to create a halt decider that:

Accepts any and all non-halting inputs and Rejects any and all halting 
inputs, then making a halt decider that runs its inputs until it detects 
that they would not halt does the trick.

> B/  if HALT waits for prog(inp) to halt it wouldnt return an answer

It doesn't simply wait it watches a single step debug trace of its input 
and as soon as it detects non-halting behavior it stops the debug trace 
and reports non-halting.

-- 
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

SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-28 17:36 -0700
  Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-28 20:24 -0500
    Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-28 19:44 -0700
      Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-28 22:17 -0500
        Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-28 23:13 -0700
          Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-29 07:14 -0500
            Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-29 05:49 -0700
              Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-29 07:57 -0500
            Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-29 08:51 -0400
              Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-29 08:04 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-29 09:22 -0400
                Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-29 10:22 -0700
              Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-29 15:39 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-30 00:13 -0400
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-29 23:51 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-30 09:12 -0400
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-30 11:05 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-30 16:27 -0400
                Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-30 14:44 -0700
                Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-30 18:50 -0400
                Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-30 16:04 -0700
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-30 16:58 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-30 18:43 -0400
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-30 19:00 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-30 17:07 -0700
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-30 19:14 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-30 17:29 -0700
                Re: SOLUTION TO THE HALTING PROBLEM! Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-31 01:26 +0000
                Re: SOLUTION TO THE HALTING PROBLEM! Richard Damon <Richard@Damon-Family.org> - 2020-10-30 22:46 -0400
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-30 22:14 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-30 20:25 -0700
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-30 22:41 -0500
                Re: SOLUTION TO THE HALTING PROBLEM! Graham Cooper <grahamcooper7@gmail.com> - 2020-10-30 23:30 -0700
                Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-29 23:56 -0500
            Stop crossposting you imbecil spammer (Was: SOLUTION TO THE HALTING PROBLEM!) Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 14:01 +0100
            Re: Stop crossposting you imbecil spammer (Re: SOLUTION TO THE HALTING PROBLEM! Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 19:39 +0100
              Re: Stop crossposting you imbecil spammer (Re: SOLUTION TO THE HALTING PROBLEM! olcott <NoOne@NoWhere.com> - 2020-10-29 13:43 -0500
            Re: SOLUTION TO THE HALTING PROBLEM! Mostowski Collapse <janburse@fastmail.fm> - 2020-10-29 20:49 +0100
              Re: SOLUTION TO THE HALTING PROBLEM! Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-10-29 13:09 -0700

csiph-web