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


Groups > comp.software-eng > #2586 > unrolled thread

Detecting infinite recursion

Started byolcott <NoOne@NoWhere.com>
First post2021-02-26 13:53 -0600
Last post2021-03-09 19:42 -0600
Articles 18 on this page of 38 — 10 participants

Back to article view | Back to comp.software-eng


Contents

  Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-26 13:53 -0600
    Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-02-26 12:48 -0800
    Re: Detecting infinite recursion Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-02-26 21:37 +0000
      Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-02-26 15:26 -0800
    Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-02-27 01:58 +0000
    Re: Detecting infinite recursion Jeff Barnett <jbb@notatt.com> - 2021-02-26 21:32 -0700
    Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 14:20 -0600
    Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 14:40 -0600
      Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 21:30 -0600
      Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-02-28 13:08 -0600
        Re: Detecting infinite recursion (H_Hat is proved to be decidable) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-01 03:52 +0000
          Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 21:32 -0600
            Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-03 15:37 -0600
          Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-02 09:29 -0600
    Re: Detecting infinite recursion om@iki.fi (Otto J. Makela) - 2021-03-02 18:36 +0200
      Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 11:22 -0600
        Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 17:46 +0000
          Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 13:00 -0600
            Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 19:35 +0000
            Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 13:50 -0600
              Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 19:57 +0000
                Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 14:20 -0600
                Re: Detecting infinite recursion Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-03-02 12:57 -0800
                  Re: Detecting infinite recursion gazelle@shell.xmission.com (Kenny McCormack) - 2021-03-03 02:17 +0000
        Re: Detecting infinite recursion (credit where it is due) olcott <NoOne@NoWhere.com> - 2021-03-02 18:45 -0600
        Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 20:40 -0600
          Re: Detecting infinite recursion (halt decider spec) Richard Damon <Richard@Damon-Family.org> - 2021-03-02 21:57 -0500
            Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 21:03 -0600
              Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 21:05 -0600
              Re: Detecting infinite recursion (halt deciding criteria) olcott <NoOne@NoWhere.com> - 2021-03-03 15:50 -0600
      Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-03 12:52 -0600
      Re: Detecting infinite recursion (rewritten) olcott <NoOne@NoWhere.com> - 2021-03-03 17:06 -0600
    Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-03 12:55 -0600
    Re: Detecting infinite recursion (pathological self-reference error) olcott <NoOne@NoWhere.com> - 2021-03-06 09:58 -0600
    Re: Detecting infinite recursion Bonita Montero <Bonita.Montero@gmail.com> - 2021-03-07 16:38 +0100
      Re: Detecting infinite recursion (halting problem) olcott <NoOne@NoWhere.com> - 2021-03-07 09:55 -0600
    Refuting the halting problem proofs with fully operational code olcott <NoOne@NoWhere.com> - 2021-03-09 10:26 -0600
    Re: Detecting infinite recursion (2021-03-09) olcott <NoOne@NoWhere.com> - 2021-03-09 19:42 -0600

Page 2 of 2 — ← Prev page 1 [2]


#2606

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2021-03-02 19:57 +0000
Message-ID<20210302115219.467@kylheku.com>
In reply to#2605
On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
> On 3/2/2021 1:00 PM, olcott wrote:
>> On 3/2/2021 11:46 AM, Kaz Kylheku wrote:
>>> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
>>>> On 3/2/2021 10:36 AM, Otto J. Makela wrote:
>>>>> I'm a bit late to the discussion, but this sounds a lot like you're
>>>>> trying to overturn Turing's proof that that a general algorithm to 
>>>>> solve
>>>>> the halting problem for all possible program-input pairs cannot exist.
>>>>>
>>>>
>>>> Yes. The key brand new insight that I had about this proof is that the
>>>> actual execution trace never reaches the undecidable portion, thus
>>>
>>> The program has no "undecidable portion". We know perfectly well
>>> whether it terminates or not, because it is trivial.
>>>
>
> There is a much earlier attribution to the same person:
>
> sci.logic   Daryl McCullough  June 25, 2004
> On Friday, June 25, 2004 at 6:30:39 PM UTC-5, Daryl McCullough wrote:
> > You ask someone (we'll call him "Jack") to give a truthful
> > yes/no answer to the following question:
> > Will Jack's answer to this question be no?
> > Jack can't possibly give a correct yes/no answer to the question.
>
> https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
>
> Jack cannot possibly provide a correct answer because both answers of 
> "yes" and "no" form a contradiction.

What you're perpetually missing is that a mathematical or
computatational function isn't Jack. If it gives a "yes" answer for some
input, it can give no other answer. Functions don't have the choice of
re-evaluating their answer and changing it.

Much of your rhetoric in this direction is laced with
anthropomorphic fallacy.

If we edit a function to give a different answer for the same input,
we are creating a different function. Since the input is the function
itself, the input has changed too!

You continue to be confused by this point; your work history consists
of producing different versions of code under the same names, taking
different inputs under the same name, and speaking about it in terms as
if they are all one thing.

[toc] | [prev] | [next] | [standalone]


#2607

Fromolcott <NoOne@NoWhere.com>
Date2021-03-02 14:20 -0600
Message-ID<iK2dndfzIPBlAKP9nZ2dnUU7-WfNnZ2d@giganews.com>
In reply to#2606
On 3/2/2021 1:57 PM, Kaz Kylheku wrote:
> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
>> On 3/2/2021 1:00 PM, olcott wrote:
>>> On 3/2/2021 11:46 AM, Kaz Kylheku wrote:
>>>> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
>>>>> On 3/2/2021 10:36 AM, Otto J. Makela wrote:
>>>>>> I'm a bit late to the discussion, but this sounds a lot like you're
>>>>>> trying to overturn Turing's proof that that a general algorithm to
>>>>>> solve
>>>>>> the halting problem for all possible program-input pairs cannot exist.
>>>>>>
>>>>>
>>>>> Yes. The key brand new insight that I had about this proof is that the
>>>>> actual execution trace never reaches the undecidable portion, thus
>>>>
>>>> The program has no "undecidable portion". We know perfectly well
>>>> whether it terminates or not, because it is trivial.
>>>>
>>
>> There is a much earlier attribution to the same person:
>>
>> sci.logic   Daryl McCullough  June 25, 2004
>> On Friday, June 25, 2004 at 6:30:39 PM UTC-5, Daryl McCullough wrote:
>>> You ask someone (we'll call him "Jack") to give a truthful
>>> yes/no answer to the following question:
>>> Will Jack's answer to this question be no?
>>> Jack can't possibly give a correct yes/no answer to the question.
>>
>> https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ
>>
>> Jack cannot possibly provide a correct answer because both answers of
>> "yes" and "no" form a contradiction.
> 
> What you're perpetually missing is that a mathematical or
> computatational function isn't Jack. If it gives a "yes" answer for some
> input, it can give no other answer. Functions don't have the choice of
> re-evaluating their answer and changing it.
> 
> Much of your rhetoric in this direction is laced with
> anthropomorphic fallacy.
> 
> If we edit a function to give a different answer for the same input,
> we are creating a different function. Since the input is the function
> itself, the input has changed too!
> 
> You continue to be confused by this point; your work history consists
> of producing different versions of code under the same names, taking
> different inputs under the same name, and speaking about it in terms as
> if they are all one thing.
> 

// P has the machine address of H_Hat()
void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
   return;
}

Although you may endlessly dodge this point it remains perfectly true 
that both possible Boolean return values from Halts() to H_Hat() would 
be made incorrect on the basis that they are contradicted.

It is also a verified fact that these return values are contradicted in 
the exact same pathological self-reference(Olcott 2004) way that makes 
it impossible for Jack to provide a correct answer to this question:
Is the answer to this question no?





-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2608

FromKeith Thompson <Keith.S.Thompson+u@gmail.com>
Date2021-03-02 12:57 -0800
Message-ID<874khtjmtv.fsf@nosuchdomain.example.com>
In reply to#2606
Kaz Kylheku <563-365-8930@kylheku.com> writes:
> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
[more of the same]

Kaz, olcott's article to which you replied was posted to
comp.theory, comp.lang.c, comp.lang.c++, and comp.software-eng,
with followups directed to comp.lang.c.  Your followup ignored the
"Followup-To: comp.theory" header line and cross-posted to all
four newsgroups.

Is your newsreader buggy, or are you deliberately making
inappropriate cross-posts, or is something else going on?

I've cross-posted this article and set followups to comp.theory only.

-- 
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

[toc] | [prev] | [next] | [standalone]


#2610

Fromgazelle@shell.xmission.com (Kenny McCormack)
Date2021-03-03 02:17 +0000
Message-ID<s1mrki$3dqs5$1@news.xmission.com>
In reply to#2608
In article <874khtjmtv.fsf@nosuchdomain.example.com>,
Keith Thompson  <Keith.S.Thompson+u@gmail.com> wrote:
>Kaz Kylheku <563-365-8930@kylheku.com> writes:
>> On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
>[more of the same]
>
>Kaz, olcott's article to which you replied was posted to
>comp.theory, comp.lang.c, comp.lang.c++, and comp.software-eng,
>with followups directed to comp.lang.c.  Your followup ignored the
>"Followup-To: comp.theory" header line and cross-posted to all
>four newsgroups.
>
>Is your newsreader buggy, or are you deliberately making
>inappropriate cross-posts, or is something else going on?
>
>I've cross-posted this article and set followups to comp.theory only.

Wow.  I'm so impressed.

-- 
People who want to share their religious views with you
almost never want you to share yours with them. -- Dave Barry

[toc] | [prev] | [next] | [standalone]


#2609 — Re: Detecting infinite recursion (credit where it is due)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-02 18:45 -0600
SubjectRe: Detecting infinite recursion (credit where it is due)
Message-ID<qpudnYflr7K3QaP9nZ2dnUU7-enNnZ2d@giganews.com>
In reply to#2601
On 3/2/2021 6:20 PM, Richard Damon wrote:
> On 3/2/21 5:59 PM, olcott wrote:
>> On 3/2/2021 4:50 PM, Richard Damon wrote:
>>> On 3/2/21 5:24 PM, olcott wrote:
>>>> On 3/2/2021 3:07 PM, Richard Damon wrote:
>>>>> On 3/2/21 3:41 PM, olcott wrote:
>>>>>> On 3/2/2021 2:01 PM, Malcolm McLean wrote:
>>>>>>> On Tuesday, 2 March 2021 at 19:52:39 UTC, olcott wrote:
>>>>>>>> On 3/2/2021 1:45 PM, Siri Cruise wrote:
>>>>>>>>> In article <uLSdnZF1Hv7L6aP9...@giganews.com>,
>>>>>>>>> olcott <No...@NoWhere.com> wrote:
>>>>>>>>>
>>>>>>>>>> Yes. The key brand new insight that I had about this proof is
>>>>>>>>>> that the
>>>>>>>>>
>>>>>>>>> It's easy to express some number theory conjectures as recursive
>>>>>>>>> procedures that either never halt if the conjecture is true or do
>>>>>>>>> halt (on a counterexample) if the conjecture is false. If you
>>>>>>>>> really can solve the halting problem, then solve these and be
>>>>>>>>> famous for solving all number theory conjectures and
>>>>>>>>> simultaneously proving number theory is w-inconsistent.
>>>>>>>>>
>>>>>>>> My background is computer science not mathematics, I will leave the
>>>>>>>> math
>>>>>>>> aspects of this as an exercise for the reader on the basis of the
>>>>>>>> computer science solution that I have provided.
>>>>>>>>
>>>>>>> All you really need to know is that, if you could write a halt
>>>>>>> decider, then
>>>>>>> many problems considered by mathematicians to be insoluble would
>>>>>>> suddenly become soluble. That tells you that it's likely that there
>>>>>>> are issues
>>>>>>> in writing a halt decider which are at least as hard to resolve as
>>>>>>> finding
>>>>>>> solutions to all these previously insoluble maths problems. Otherwise
>>>>>>> mathematicians really aren't such a smart bunch.
>>>>>>>
>>>>>>> That's an informal argument, not a proof.
>>>>>>>
>>>>>>
>>>>>> I have been working on this for thousands and thousands of hours since
>>>>>> 2004. This is best documented in my thousands and thousands of
>>>>>> posts to
>>>>>> comp.theory.
>>>>>>
>>>>>> My solution is so simple that it is very obviously totally correct.
>>>>>> It is obvious that the standard halting problem proof counter-example
>>>>>> would infinitely invoke the halt decider.
>>>>>>
>>>>>> When the halt decider has been augmented to be able to see this
>>>>>> then it
>>>>>> can correctly decide halting on the conventional HP proof
>>>>>> counter-examples.
>>>>>>
>>>>>>
>>>>>> int Halts(u32 P, u32 I)
>>>>>> {
>>>>>>      ((void(*)(int))P)(I);
>>>>>>      return 1;
>>>>>> }
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>>      u32 Input_Halts = Halts(P, P);
>>>>>>      if (Input_Halts)
>>>>>>        HERE: goto HERE;
>>>>>>      return;
>>>>>> }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>      u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>>>>>      Output("Input_Would_Halt = ", Input_Would_Halt);
>>>>>> }
>>>>>>
>>>>>>
>>>>
>>>> What was that counter-example that you presented that showed there was
>>>> an exception to the rule that when there is a sequence of two function
>>>> calls to the same function from the same machine address and no
>>>> conditional branch instructions inbetween that it might possibly not be
>>>> infinite recursion? This exception made me have to start looking at
>>>> inputs to function call.
>>>>
>>>>
>>>
>>> Ultimately the issue is that if you allow the use of any data base
>>> program flow control, even if not what you were calling a 'conditional
>>> jump' you can get the effect of a conditional jump.
>>>
>>> Since your simulation routine is in effect, such a program flow
>>> instruction (even if you don't want to call it that, especially inside
>>> you 'OS Code') I was able to defeat your incorrect rule (incorrect as it
>>> doesn't restrict the conditions enough) by entering one program with
>>> different data so it could use that data to create differing program
>>> flow after the call that you were detecting as recursive without
>>> conditional (because there WAS a conditional execution in the loop).
>>>
>>> Your modified rule is basicly roughly the detection of a loop by seeing
>>> the program return to a previous state with ALL the state being the same
>>> (which holds even with conditionals in the path). At the simulate call,
>>> assuming that you do block access to global variable, the state that
>>> crosses is limited, so is easier to check.
>>>
>>> Note that since it appears that Halts does have some access to global
>>> data, that condition isn't fully satisfied, but it may be you are
>>> preventing that information from leaking out enough for your purposes.
>>>
>>
>> That is not the specific concrete example that you previously provided.
>> Since I remember that this caused me to build the infrastructure to make
>> sure that I examined inputs to a function your concrete example had
>> different inputs. Maybe it was something like the second input was a
>> value used by a switch statement.
>>
> 
> That is an exact decsription of what I did (A switch would have been a
> conditional).
> 
> It worked by passing different values of the data parameter that the
> function use as the program parameter, thus getting the Halt Decider
> function to perform the conditional execution instruction cloaked behind
> your false wall of separation.
> 

OK, great. That was an important critique. It caused me to focus on 
examining to input to functions as a key element of halt deciding.

Assuming that what Malcolm said also applies to indirect recursion:
On 2/26/2021 2:41 PM, Malcolm McLean wrote:
 > If A calls itself with exactly the same data as it was
 > originally invoked with, then it must be infinitely recursive,
 > even if there are conditional branches. It always takes the
 > same branches.

Then detecting infinite recursion is made even simpler.

Noticing that the H_Hat() invocation of Halts() is infinitely recursive 
for every halt decider that bases it halt deciding decision on examining 
its own simulation of its input overcame the "impossible" aspect of 
refuting the halting problem proofs. (Copyright Pete Olcott 2016, 2017).

The feedback that you and Malcolm provided was important to implementing 
this halt decider. You corrected a key short-coming with the initial 
halt decider design and Malcolm eliminated an unnecessary step.

void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
   return;
}

int main()
{
   u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
   Output("Input_Would_Halt = ", Input_Would_Halt);
}

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2611 — Re: Detecting infinite recursion (halt decider spec)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-02 20:40 -0600
SubjectRe: Detecting infinite recursion (halt decider spec)
Message-ID<e7KdnSq4JLWfaqP9nZ2dnUU7-THNnZ2d@giganews.com>
In reply to#2601
On 3/2/2021 8:25 PM, Richard Damon wrote:
> On 3/2/21 8:48 PM, olcott wrote:
>> On 3/2/2021 7:44 PM, Richard Damon wrote:
>>> On 3/2/21 5:38 PM, olcott wrote:
>>>> On 3/2/2021 4:15 PM, Richard Damon wrote:
>>>>> On 3/2/21 4:19 PM, olcott wrote:
>>>>>> On 3/2/2021 3:01 PM, Alan Mackenzie wrote:
>>>>>>> olcott <NoOne@nowhere.com> wrote:
>>>>>>>
>>>>>>> [ .... ]
>>>>>>>
>>>>>>>> I have been working on this for thousands and thousands of hours
>>>>>>>> since
>>>>>>>> 2004. This is best documented in my thousands and thousands of
>>>>>>>> posts to
>>>>>>>> comp.theory.
>>>>>>>
>>>>>>> So what?  It doesn't mean you've got anything right.
>>>>>>>
>>>>>>>> My solution is so simple that it is very obviously totally correct.
>>>>>>>
>>>>>>> Your "solution" is so wrong that everybody apart from you sees it
>>>>>>> immediately.
>>>>>>>
>>>>>>>> It is obvious that the standard halting problem proof
>>>>>>>> counter-example
>>>>>>>> would infinitely invoke the halt decider.
>>>>>>>
>>>>>>> It is not.
>>>>>>>
>>>>>>>> When the halt decider has been augmented to be able to see this
>>>>>>>> then it
>>>>>>>> can correctly decide halting on the conventional HP proof
>>>>>>>> counter-examples.
>>>>>>>
>>>>>>> That totally misunderstands both the halting problem and its proof.
>>>>>>> That is that there is no halting decider which can decide ALL Turing
>>>>>>> machines.  Given a purported universal halting decider, a simple
>>>>>>> procedure produces a machine which that purported decider cannot
>>>>>>> correctly decide.  You don't get to modify the "decider" after the
>>>>>>> fact
>>>>>>> to decide that counterexample.
>>>>>>
>>>>>> When I talk about augmenting the halt decider this is only so that
>>>>>> I can
>>>>>> construct the idea of the complete halt decider incrementally in the
>>>>>> minds of my readers. By explaining this in incemental steps of further
>>>>>> elaboration I avoid overwhelming my readers with too much detail.
>>>>>>
>>>>>> It is only the actual complete halt decider that actually does the
>>>>>> halt
>>>>>> deciding.
>>>>>>
>>>>>> The fact that this completed halt decider correctly decides halting
>>>>>> for
>>>>>> H_Hat() refutes the conventional halting problem proofs.
>>>>>>
>>>>>> void H_Hat(u32 P)
>>>>>> {
>>>>>>      u32 Input_Halts = Halts(P, P);
>>>>>>      if (Input_Halts)
>>>>>>        HERE: goto HERE;
>>>>>>      return;
>>>>>> }
>>>>>>
>>>>>> int main()
>>>>>> {
>>>>>>      u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>>>>>      Output("Input_Would_Halt = ", Input_Would_Halt);
>>>>>> }
>>>>>>
>>>>>>
>>>>>
>>>>> Except for the fact that it gives the wrong answer when H_Hat is run
>>>>> properly?
>>>>>
>>>>
>>>> When the halt decider is designed to report non-halting behavior as soon
>>>> as it detects non-halting behavior then both the above invocation and
>>>> the following invocation do meet this spec.
>>>>
>>>> int main()
>>>> {
>>>>      H_Hat((u32)H_Hat);
>>>> }
>>>>
>>>> Here is the full execution trace of that last one:
>>>>
>>>> _H_Hat()
>>>> [00000878](01)  55              push ebp
>>>> [00000879](02)  8bec            mov ebp,esp
>>>> [0000087b](01)  51              push ecx
>>>> [0000087c](03)  8b4508          mov eax,[ebp+08]
>>>> [0000087f](01)  50              push eax
>>>> [00000880](03)  8b4d08          mov ecx,[ebp+08]
>>>> [00000883](01)  51              push ecx
>>>> [00000884](05)  e87ffeffff      call 00000708
>>>> [00000889](03)  83c408          add esp,+08
>>>> [0000088c](03)  8945fc          mov [ebp-04],eax
>>>> [0000088f](04)  837dfc00        cmp dword [ebp-04],+00
>>>> [00000893](02)  7402            jz 00000897
>>>> [00000895](02)  ebfe            jmp 00000895
>>>> [00000897](02)  8be5            mov esp,ebp
>>>> [00000899](01)  5d              pop ebp
>>>> [0000089a](01)  c3              ret
>>>>
>>>> _main()
>>>> [000008a8](01)  55              push ebp
>>>> [000008a9](02)  8bec            mov ebp,esp
>>>> [000008ab](05)  6878080000      push 00000878
>>>> [000008b0](05)  e8c3ffffff      call 00000878
>>>> [000008b5](03)  83c404          add esp,+04
>>>> [000008b8](02)  33c0            xor eax,eax
>>>> [000008ba](01)  5d              pop ebp
>>>> [000008bb](01)  c3              ret
>>>>
>>>> ===============================
>>>> ...[000008a8][000111a5][00000000](01)  55              push ebp
>>>> ...[000008a9][000111a5][00000000](02)  8bec            mov ebp,esp
>>>> ...[000008ab][000111a1][00000878](05)  6878080000      push 00000878
>>>> ...[000008b0][0001119d][000008b5](05)  e8c3ffffff      call 00000878
>>>> ...[00000878][00011199][000111a5](01)  55              push ebp
>>>> ...[00000879][00011199][000111a5](02)  8bec            mov ebp,esp
>>>> ...[0000087b][00011195][00000000](01)  51              push ecx
>>>> ...[0000087c][00011195][00000000](03)  8b4508          mov eax,[ebp+08]
>>>> ...[0000087f][00011191][00000878](01)  50              push eax
>>>> ...[00000880][00011191][00000878](03)  8b4d08          mov ecx,[ebp+08]
>>>> ...[00000883][0001118d][00000878](01)  51              push ecx
>>>> ...[00000884][00011189][00000889](05)  e87ffeffff      call 00000708
>>>> Begin Local Halt Decider Simulation at Machine Address:878
>>>> ...[00000878][00031225][00031229](01)  55              push ebp
>>>> ...[00000879][00031225][00031229](02)  8bec            mov ebp,esp
>>>> ...[0000087b][00031221][000211f5](01)  51              push ecx
>>>> ...[0000087c][00031221][000211f5](03)  8b4508          mov eax,[ebp+08]
>>>> ...[0000087f][0003121d][00000878](01)  50              push eax
>>>> ...[00000880][0003121d][00000878](03)  8b4d08          mov ecx,[ebp+08]
>>>> ...[00000883][00031219][00000878](01)  51              push ecx
>>>> ...[00000884][00031215][00000889](05)  e87ffeffff      call 00000708
>>>> ...[00000878][000423cd][000423d1](01)  55              push ebp
>>>> ...[00000879][000423cd][000423d1](02)  8bec            mov ebp,esp
>>>> ...[0000087b][000423c9][0003239d](01)  51              push ecx
>>>> ...[0000087c][000423c9][0003239d](03)  8b4508          mov eax,[ebp+08]
>>>> ...[0000087f][000423c5][00000878](01)  50              push eax
>>>> ...[00000880][000423c5][00000878](03)  8b4d08          mov ecx,[ebp+08]
>>>> ...[00000883][000423c1][00000878](01)  51              push ecx
>>>> ...[00000884][000423bd][00000889](05)  e87ffeffff      call 00000708
>>>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped
>>>> ...[00000889][00011195][00000000](03)  83c408          add esp,+08
>>>> ...[0000088c][00011195][00000000](03)  8945fc          mov [ebp-04],eax
>>>> ...[0000088f][00011195][00000000](04)  837dfc00        cmp dword
>>>> [ebp-04],+00
>>>> ...[00000893][00011195][00000000](02)  7402            jz 00000897
>>>> ...[00000897][00011199][000111a5](02)  8be5            mov esp,ebp
>>>> ...[00000899][0001119d][000008b5](01)  5d              pop ebp
>>>> ...[0000089a][000111a1][00000878](01)  c3              ret
>>>> ...[000008b5][000111a5][00000000](03)  83c404          add esp,+04
>>>> ...[000008b8][000111a5][00000000](02)  33c0            xor eax,eax
>>>> ...[000008ba][000111a9][00010000](01)  5d              pop ebp
>>>> ...[000008bb][000111ad][00000098](01)  c3              ret
>>>> Number_of_User_Instructions(39)
>>>>
>>>>
>>>>
>>>
>>> What, the fact that it said the program was 'non-halting' and the
>>> program stopped is a correct Halting Behavior answer?
>>
>> You can now see exactly what it does and that it does this correctly no
>> weasel words are able to correctly deny this. H_Hat() does specify
>> infinite recursion and as soon as the halt decider is allowed to see
>> this that is what it decides.
>>
>>
> 
> H_Hat does NOT specify infinite recursion, at least not if Halts is a
> proper Halt Decider, because then Halts MUST terminate in finite time,
> and thus can NOT have infinite Recursion.
> 
> If anything, Halts has infinite recursion, because it invoked H_Hat
> which calls Halts, and Halts has no such promise about the behavior of
> the provided program (in fact, it is part of its job to find out).
> Therefore, if Halts fails to handle this, and gets into an infinite
> recursion, the IT has failed at its job.
> 
> So, at best, Halts can detect that IT has failed at its job, which is
> what the recursion shows.
> 
> This can be shown with the utimate test, we run Halts(H_Hat, H_Hat) and
> by your discription, is says non-halting. We then run H_Hat(H_Hat) and
> (assuming Halts returns the same answer) it halts, and thus Halts has
> been proven to be wrong.
> 

When Halts() is designed to detect what would otherwise be infinite 
recursion if Halts() did not abort the simulation of its input then 
Halts() has met its design spec.

This same design can be used by operating systems to prevent themselves 
from wasting resources.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2612 — Re: Detecting infinite recursion (halt decider spec)

FromRichard Damon <Richard@Damon-Family.org>
Date2021-03-02 21:57 -0500
SubjectRe: Detecting infinite recursion (halt decider spec)
Message-ID<eWC%H.4285$131.823@fx46.iad>
In reply to#2611
On 3/2/21 9:40 PM, olcott wrote:
> 
> When Halts() is designed to detect what would otherwise be infinite
> recursion if Halts() did not abort the simulation of its input then
> Halts() has met its design spec.
> 
> This same design can be used by operating systems to prevent themselves
> from wasting resources.

Which shows you do NOT understand the Mathematical concept of the
Halting Problem. Maybe in you computer programming career you haven't
needed to write a program that asks if another program will run to
completion or not, but THAT is part of the goal of the Halting Problem.

IT is really a problem with use in Theoretical Computer Science or
Number Theory and related fields, not practical Computer Science. The
detection of 'stuck programs' isn't that interesting of a problem and
is, I believe, considered reasonably well solved (the biggest problem is
that the cost to implement most solutions costs you so much more
computing power than you save with the occational 'rogue' program, that
it isn't worth implementing in common code. You let a human decide that
there is a problem and they can kill the code.

[toc] | [prev] | [next] | [standalone]


#2613 — Re: Detecting infinite recursion (halt decider spec)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-02 21:03 -0600
SubjectRe: Detecting infinite recursion (halt decider spec)
Message-ID<v7GdnQE-eaEdYaP9nZ2dnUU7-X_NnZ2d@giganews.com>
In reply to#2612
On 3/2/2021 8:57 PM, Richard Damon wrote:
> On 3/2/21 9:40 PM, olcott wrote:
>>
>> When Halts() is designed to detect what would otherwise be infinite
>> recursion if Halts() did not abort the simulation of its input then
>> Halts() has met its design spec.
>>
>> This same design can be used by operating systems to prevent themselves
>> from wasting resources.
> 
> Which shows you do NOT understand the Mathematical concept of the
> Halting Problem. Maybe in you computer programming career you haven't
> needed to write a program that asks if another program will run to
> completion or not, but THAT is part of the goal of the Halting Problem.
> 
> IT is really a problem with use in Theoretical Computer Science or
> Number Theory and related fields, not practical Computer Science. The
> detection of 'stuck programs' isn't that interesting of a problem and
> is, I believe, considered reasonably well solved (the biggest problem is
> that the cost to implement most solutions costs you so much more
> computing power than you save with the occational 'rogue' program, that
> it isn't worth implementing in common code. You let a human decide that
> there is a problem and they can kill the code.
> 

As long as this single instance of the conventional halting problem 
proof counter-examples can be correctly decided this refutes these 
proofs. There is no wiggle room around this.


void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
   return;
}


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2614 — Re: Detecting infinite recursion (halt decider spec)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-02 21:05 -0600
SubjectRe: Detecting infinite recursion (halt decider spec)
Message-ID<v7GdnQA-eaF1YaP9nZ2dnUU7-X-dnZ2d@giganews.com>
In reply to#2613
On 3/2/2021 9:03 PM, olcott wrote:
> On 3/2/2021 8:57 PM, Richard Damon wrote:
>> On 3/2/21 9:40 PM, olcott wrote:
>>>
>>> When Halts() is designed to detect what would otherwise be infinite
>>> recursion if Halts() did not abort the simulation of its input then
>>> Halts() has met its design spec.
>>>
>>> This same design can be used by operating systems to prevent themselves
>>> from wasting resources.
>>
>> Which shows you do NOT understand the Mathematical concept of the
>> Halting Problem. Maybe in you computer programming career you haven't
>> needed to write a program that asks if another program will run to
>> completion or not, but THAT is part of the goal of the Halting Problem.
>>
>> IT is really a problem with use in Theoretical Computer Science or
>> Number Theory and related fields, not practical Computer Science. The
>> detection of 'stuck programs' isn't that interesting of a problem and
>> is, I believe, considered reasonably well solved (the biggest problem is
>> that the cost to implement most solutions costs you so much more
>> computing power than you save with the occational 'rogue' program, that
>> it isn't worth implementing in common code. You let a human decide that
>> there is a problem and they can kill the code.
>>
> 
> As long as this single instance of the conventional halting problem 
> proof counter-examples can be correctly decided 

by Halts()

> this refutes these 
> proofs. There is no wiggle room around this.
> 
> 
> void H_Hat(u32 P)
> {
>    u32 Input_Halts = Halts(P, P);
>    if (Input_Halts)
>      HERE: goto HERE;
>    return;
> }
> 
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2620 — Re: Detecting infinite recursion (halt deciding criteria)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-03 15:50 -0600
SubjectRe: Detecting infinite recursion (halt deciding criteria)
Message-ID<fqqdndRzTqYomd39nZ2dnUU78IvNnZ2d@giganews.com>
In reply to#2613
On 3/3/2021 3:41 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> As soon as this criteria is met a non-halting computation has been determined:
>>
>> -On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
>> -> A computation that would not halt if its simulation were not
>> -> halted is indeed a non-halting computation.
> 
> You used to quote this sentence when you were re-defining what it means
> for a computation to be a halting one.  Given that you are still quoting
> it can we take it that you have not changed your mind about this and you
> are still using your own criterion for what is a halting computation?
> 
> I need to ask because you don't understand what I said, so your quoting
> it does not mean you agree with me.
> 

To mean it means exactly what it says, did you intend it to not mean 
exactly what it says?

When so ever it is known that a computation would not halt unless its 
simulation was halted [exactly and precisely the above criteria]

the simulator can stop simulating its input and report not halting.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2617

Fromolcott <NoOne@NoWhere.com>
Date2021-03-03 12:52 -0600
Message-ID<bs-dnel06bxoR6L9nZ2dnUU7-c_NnZ2d@giganews.com>
In reply to#2600
On 3/3/2021 1:58 AM, David Brown wrote:
> On 03/03/2021 08:23, Juha Nieminen wrote:
>> In comp.lang.c++ Otto J. Makela <om@iki.fi> wrote:
>>> I'm a bit late to the discussion, but this sounds a lot like you're
>>> trying to overturn Turing's proof that that a general algorithm to solve
>>> the halting problem for all possible program-input pairs cannot exist.
>>
>> If the halting problem could be solved, it would be great news for
>> mathematics. Pretty much all unsolved problems in mathematics, at least
>> those that can be computed with an algorithm, would be solved in one
>> fell swoop.
>>
>> The Riemann hypothesis? Simply create a program that checks every
>> single non-trivial zero of the zeta function and stops when it finds
>> one that's not on the critical line. Then simply use the marvelous
>> halting problem solution above to see if it ever terminates, and
>> you'll have proven the Riemann hypothesis as true or false.
>>
>> Do odd perfect numbers exist? Simply create a program that goes
>> through every odd number and checks if it's perfect, and terminates
>> when it finds one. Use the halting problem proof to check if it will
>> ever terminate and you'll have solved the problem.
>>
>> Collatz conjecture? Same thing. And so on and so forth.
>>
> 
> I think Pete Olcott already said that he was not a mathematician.  So
> that means he is not constrained by such simple mathematical logic, and
> can solve the impossible in an way that mathematicians cannot.
> 
> You know, in the same way that non-physicists are not constrained by
> physical laws that they don't understand, and can thus make moon rockets
> in their garage powered by gravity-repulsive paint.
> 

void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
   return;
}

All of the halting problem proofs are based on the fact that it is 
impossible for Halts() to return a correct halting decision to H_Hat() 
because H_Hat() contradicts whatever value that Halts() returns.

All of these same proofs ignore the fact that every halt decider that 
bases its halt decision on examining the execution trace of its own 
simulation of its input never reaches the point in the execution trace 
where it would return a value to H_Hat().

 >> On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 >>> A computation that would not halt if its simulation were not
 >>> halted is indeed a non-halting computation.

That I have shown how a halt decider could examine such an execution 
trace to determine that its input would not halt unless the simulation 
of this input was terminated proves that these computations are halt 
decidable.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2621 — Re: Detecting infinite recursion (rewritten)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-03 17:06 -0600
SubjectRe: Detecting infinite recursion (rewritten)
Message-ID<IfmdnW1VvsnMi939nZ2dnUU78b3NnZ2d@giganews.com>
In reply to#2600
On 3/3/2021 4:18 PM, Keith Thompson wrote:
> Juha Nieminen <nospam@thanks.invalid> writes:
>> mickspud@potatofield.co.uk wrote:
>>>> Let me ask it this way: Why do you consider a fraction, like 1/3,
>>>> to be a definable number?
>>>
>>> It has a quantifiable value.
>>
>> What does that even mean?
>>
>> I think you are making stuff up as you go.
> 
> I think he's making stuff up that has even less to do with C++ than the
> original topic of this thread.  I suggest not replying.
> 

Here is the original topic of this thread completely rewritten.

Criteria for deciding that H_Hat() calls Simulate() in infinite 
recursion. I need to have this criteria validated.

(1) The execution trace of H_Hat() shows that it calls Simulate() from 
the same machine address two times in sequence with the same data.

(2) It is assumed that Simulate() either directly invokes its input (as 
shown below) or  Simulate() emulates the execution of the x86 machine 
language of its input (functionally equivalent to the direct execution 
shown below).

Does everyone agree that the above criteria is sufficient to definitely 
decide that H_Hat() is infinitely recursive?


#include <stdint.h>
#define u32 uint32_t


int Simulate(u32 P, u32 I)
{
   ((void(*)(u32))P)(I);
}


void H_Hat(u32 P)
{
   Simulate(P, P);
}


int main()
{
   Simulate((u32)H_Hat, (u32)H_Hat);
}


_Simulate()
[00000478](01)  55              push ebp
[00000479](02)  8bec            mov ebp,esp
[0000047b](03)  8b450c          mov eax,[ebp+0c]
[0000047e](01)  50              push eax
[0000047f](03)  ff5508          call dword [ebp+08]
[00000482](03)  83c404          add esp,+04
[00000485](01)  5d              pop ebp
[00000486](01)  c3              ret

_H_Hat()
[00000868](01)  55              push ebp
[00000869](02)  8bec            mov ebp,esp
[0000086b](03)  8b4508          mov eax,[ebp+08]
[0000086e](01)  50              push eax
[0000086f](03)  8b4d08          mov ecx,[ebp+08]
[00000872](01)  51              push ecx
[00000873](05)  e800fcffff      call 00000478
[00000878](03)  83c408          add esp,+08
[0000087b](01)  5d              pop ebp
[0000087c](01)  c3              ret

_main()
[00000888](01)  55              push ebp
[00000889](02)  8bec            mov ebp,esp
[0000088b](05)  6868080000      push 00000868
[00000890](05)  6868080000      push 00000868
[00000895](05)  e8defbffff      call 00000478
[0000089a](03)  83c408          add esp,+08
[0000089d](02)  33c0            xor eax,eax
[0000089f](01)  5d              pop ebp
[000008a0](01)  c3              ret


Columns
(1) Sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text

(01)[00000888][00011194][00000000](01)  55              push ebp
(02)[00000889][00011194][00000000](02)  8bec            mov ebp,esp
(03)[0000088b][00011190][00000868](05)  6868080000      push 00000868
(04)[00000890][0001118c][00000868](05)  6868080000      push 00000868
(05)[00000895][00011188][0000089a](05)  e8defbffff      call 00000478
(06)[00000868][00011178][00011184](01)  55              push ebp
(07)[00000869][00011178][00011184](02)  8bec            mov ebp,esp
(08)[0000086b][00011178][00011184](03)  8b4508          mov eax,[ebp+08]
(09)[0000086e][00011174][00000868](01)  50              push eax
(10)[0000086f][00011174][00000868](03)  8b4d08          mov ecx,[ebp+08]
(11)[00000872][00011170][00000868](01)  51              push ecx
(12)[00000873][0001116c][00000878](05)  e800fcffff      call 00000478

Line (09) pushes second parameter to Simulate() machine address 0x878
Line (11) pushes  first parameter to Simulate() machine address 0x878
Line (12) Calls Simulate(0x878, 0x878);

(13)[00000868][0001115c][00011168](01)  55              push ebp
(14)[00000869][0001115c][00011168](02)  8bec            mov ebp,esp
(15)[0000086b][0001115c][00011168](03)  8b4508          mov eax,[ebp+08]
(16)[0000086e][00011158][00000868](01)  50              push eax
(17)[0000086f][00011158][00000868](03)  8b4d08          mov ecx,[ebp+08]
(18)[00000872][00011154][00000868](01)  51              push ecx
(19)[00000873][00011150][00000878](05)  e800fcffff      call 00000478

Line (16) pushes second parameter to Simulate() machine address 0x878
Line (18) pushes  first parameter to Simulate() machine address 0x878
Line (19) Calls Simulate(0x878, 0x878);

(20)[00000868][00011140][0001114c](01)  55              push ebp
(21)[00000869][00011140][0001114c](02)  8bec            mov ebp,esp
(22)[0000086b][00011140][0001114c](03)  8b4508          mov eax,[ebp+08]
(23)[0000086e][0001113c][00000868](01)  50              push eax
(24)[0000086f][0001113c][00000868](03)  8b4d08          mov ecx,[ebp+08]
(25)[00000872][00011138][00000868](01)  51              push ecx
(26)[00000873][00011134][00000878](05)  e800fcffff      call 00000478

Line (23) pushes second parameter to Simulate() machine address 0x878
Line (25) pushes  first parameter to Simulate() machine address 0x878
Line (26) Calls Simulate(0x878, 0x878);

Now we have seen that Simulate() is invoked two times from the same 
machine address of H_Hat() with the same data. We also know that 
Simulate() either executes or emulates the machine language of its input 
and nothing more. This seems to provide a sufficient basis for deciding 
that H_Hat() is infinitely recursive, thus non-halting.



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2618

Fromolcott <NoOne@NoWhere.com>
Date2021-03-03 12:55 -0600
Message-ID<bs-dneh06bwARqL9nZ2dnUU7-c-dnZ2d@giganews.com>
In reply to#2586
On 3/3/2021 6:37 AM, Juha Nieminen wrote:
> mickspud@potatofield.co.uk wrote:
>> On Wed, 3 Mar 2021 11:53:57 +0200
>> Paavo Helde <myfirstname@osa.pri.ee> wrote:
>>> 03.03.2021 11:11 mickspud@potatofield.co.uk kirjutas:
>>>>
>>>> Strictly speaking pi is an irrational number so doesn't actually have
>>>> a definable value in the first place :)
>>>
>>> You are confusing "definable" with "exactly representable in my favorite
>>> notation".
>>
>> It would appear you are confusing definable with representable. Infinity
>> can be represented, that doesn't mean it can be defined especially given
>> there are numerous different types.
> 
> Maybe you should specify what you mean by "definable".
> 
> The number pi can certainly be defined in a completely unambiguous way
> with a finite expression. Just because it may have an infinite non-recurring
> decimal expansion doesn't mean it can't be defined.
> 
> https://en.wikipedia.org/wiki/Definable_real_number
> 
> There exist real numbers that cannot be defined (with a finite expression),
> and in fact almost all real numbers are like that, but pi is not one
> of them.
> 

 >

void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
   return;
}

All of the halting problem proofs are based on the fact that it is 
impossible for Halts() to return a correct halting decision to H_Hat() 
because H_Hat() contradicts whatever value that Halts() returns.

All of these same proofs ignore the fact that every halt decider that 
bases its halt decision on examining the execution trace of its own 
simulation of its input never reaches the point in the execution trace 
where it would return a value to H_Hat().

 >> On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 >>> A computation that would not halt if its simulation were not
 >>> halted is indeed a non-halting computation.

That I have shown how a halt decider could examine such an execution 
trace to determine that its input would not halt unless the simulation 
of this input was terminated proves that these computations are halt 
decidable.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2631 — Re: Detecting infinite recursion (pathological self-reference error)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-06 09:58 -0600
SubjectRe: Detecting infinite recursion (pathological self-reference error)
Message-ID<h6udnV4PmecHO979nZ2dnUU7-f3NnZ2d@giganews.com>
In reply to#2586
On 3/6/2021 9:12 AM, Richard Damon wrote:
> On 3/6/21 10:01 AM, olcott wrote:
>> On 3/6/2021 7:58 AM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> You can understand that the reason that (at least) many decision
>>>> problems are undecidable is that both elements of the solution set:
>>>> true/false are contradicted.
>>>
>>> No.  Every single instance of any of the undecidable problems I listed
>>> has a correct yes/no answer.  Every context-free grammar either is or
>>> not ambiguous.  Every pair of TMs either compute the same function or
>>> they do not.  Every TM either writes an 'x' to its tape or it does not.
>>> These are simple and obvious problems that have no algorithmic solution.
>>>
>>> You need to stop doing linguistic gymnastics and start facing
>>> mathematical facts.
>>>
>>
>> Every single instance of any undecidable decision problem does not have
>> a solution that can be encoded because all of the answers that it can
>> provide are defined to be incorrect.
> 
> The Halting status of H_Hat IS decidable once you have provided an H
> that meets the requirements of giving an answer in Finite time.
>>
>> Every decision problem has its entire solution set defined to be a
>> Boolean value of {true, false}.
> 
> Yes, The Halting status of any true computation is True of False.
>>
>> If Halts((u32)H_Hat, (u32)H_Hat) returns true to H_Hat() meaning that
>> its input halts, H_Hat() loops making true the wrong return value.
>>
>> If Halts((u32)H_Hat, (u32)H_Hat) returns false to H_Hat() meaning that
>> its input halts, H_Hat() halts making false the wrong return value.
> 
> Yes, So Halts gets the answer wrong, but there is a answer.
> 

Because neither return value from the entire solution set of true/false 
is correct the decision problem is incorrect.

>>
>> void H_Hat(u32 P)
>> {
>>    u32 Input_Halts = Halts(P, P);
>>    if (Input_Halts)
>>      HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>    u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
>>    Output("Input_Would_Halt = ", Input_Would_Halt);
>> }
>>
>>
>> A an adapted UTM can determine whether or not an input finite string
>> represents a Turing Machine that would halt on its input without having
>> to have its simulation stopped.
>>
> 
> Which isn't the question to the classical Turing Problem, so is
> meaningless to say anything about the proofs of the impossiblity to
> universally solve the Classical Halting Problem.
> 

As soon as the pathological self-reference error is eliminated from the 
decision problem the corrected decision problem can be decided.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2632

FromBonita Montero <Bonita.Montero@gmail.com>
Date2021-03-07 16:38 +0100
Message-ID<s22s14$a1c$1@dont-email.me>
In reply to#2586
Detecting and handling infinite recursion is easy:

	__try
	{
		...
	}
	__except( GetExceptionCode() == EXCEPTION_STACK_OVERFLOW ? 
EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH )
	{
		...
	}

Hrhr.

[toc] | [prev] | [next] | [standalone]


#2633 — Re: Detecting infinite recursion (halting problem)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-07 09:55 -0600
SubjectRe: Detecting infinite recursion (halting problem)
Message-ID<CbydnYc98cTRatn9nZ2dnUU7-afNnZ2d@giganews.com>
In reply to#2632
On 3/7/2021 9:38 AM, Bonita Montero wrote:
> Detecting and handling infinite recursion is easy:
> 
>      __try
>      {
>          ...
>      }
>      __except( GetExceptionCode() == EXCEPTION_STACK_OVERFLOW ? 
> EXCEPTION_EXECUTE_HANDLER : EXCEPTION_CONTINUE_SEARCH )
>      {
>          ...
>      }
> 
> Hrhr.

I am creating a halt decider that correctly decides the conventional 
halting problem counter examples on the basis of examining the x86 
machine language execution trace of the H_Hat() invocations of Halts().

The halt decider decides that they are infinitely recursive, aborts its 
simulation of H_Hat() and decides not halting.

Halts() has as its foundation a complete fully functional x86 emulator 
that has "been on the market" for 25 years.

void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
}

int main()
{
   u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
   Output("Input_Would_Halt = ", Input_Would_Halt);
}


http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2634 — Refuting the halting problem proofs with fully operational code

Fromolcott <NoOne@NoWhere.com>
Date2021-03-09 10:26 -0600
SubjectRefuting the halting problem proofs with fully operational code
Message-ID<BfydnedSjaVdPNr9nZ2dnUU7-R_NnZ2d@giganews.com>
In reply to#2586
On 3/9/2021 10:16 AM, R Kym Horsell wrote:
> Richard Damon <Richard@damon-family.org> wrote:
>> On 3/8/21 11:28 PM, olcott wrote:
>>> I will respond to you to the extent that you critique how this:
>>> http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf
>>> is computationally equivalent to this:
>>> A halt decider UTM that simply simulates its input
>>> until its input halts on its own or the halt decider
>>> determines that its input would never halt on its own
>>> thus stops simulating it.
>>> And how that refutes the halting problem proofs.
>>> Everyting else will be construed as a dishonest dodge.
>>> I think that Ben masters the dishonest dodge in an attempt
>>> to mask his ignorance of the subject matter.
>> It claims to refute the proofs by building a strawman with a different
>> Halting Problem.
>> The decision to detect 'would never halt' is flawed in that it doesn't
>> take into account the conditional execution of the simulated halt
>> decider itself.
>> You have made the mistake of assuming the conclusion.
> 
> That happened at least when O tried to "solve" the Halting Problem
> by detecting infinite recursion -- a known equivalent problem.
> (Whether a program in general reaches any specified point on all
> inputs -- e.g. on the inside of an "if" condition where a recursive call
> happens -- is the same as the HP).
> 
> The joke part was the "halt detection" was carried out by a step-by-step
> simulator.
> 
> Whether O has himself been in a loop on this problem the last few years
> is the same as the HP and a meta joke.
> 

You can read the updated paper, I just added much more in depth analysis 
of exactly why the halting problem was previuosly considered unsolvable 
and why this never actually was the case.

I provide an actual execution trace of fully operational code to prove 
my point.

http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#2635 — Re: Detecting infinite recursion (2021-03-09)

Fromolcott <NoOne@NoWhere.com>
Date2021-03-09 19:42 -0600
SubjectRe: Detecting infinite recursion (2021-03-09)
Message-ID<kaydnXAYisSWudX9nZ2dnUU7-cednZ2d@giganews.com>
In reply to#2586
Eliminating pathological self-reference error from the halting problem

The pathological self reference error occurs whenever a question or 
decision problem cannot be correctly answered because both of the yes/no 
or true/false answers are contradicted.

If we ask Jack[1] this question: Will your answer to this question be no?
Neither answer of yes or no is correct because they are both contradicted.

When an input program is defined to do opposite of whatever the halt 
decider decides about its halt status then we have the same pathological 
self-reference error as Jack's question.

If the halt decider Halts() returns a value of true to H_Hat() then 
H_Hat() would go into an infinite loop and never halt. If the halt 
decider Halts() returns a value of false to H_Hat() then H_Hat would 
immediately stop running.

The simplest way to define a halt decider is to make a program that 
simply runs its input to see what it does. In technical terms this would 
be a universal Turing machine (UTM) that has been adapted to become a 
halt decider. This UTM would simply simulate the execution of its input 
until its input halts on its own or the halt decider determines that its 
input would never halt on its own and stops simulating it. In order for 
the UTM to see what its input does it must keep track of an execution 
trace of its input.

Every (at least partial) halt decider that decides the halting status of 
its input on the basis of its examination of the execution trace of its 
own simulation of this input would correctly decide the conventional 
halting problem counter-examples as not halting.

The x86utm operating system was created so that halt deciders written in 
the C programming language would be computationally equivalent to the 
execution of actual Turing machines. These (at least partial) halt 
deciders base their halting decision on examining the execution trace of 
the x86 machine language of their input. The input is the COFF object 
file output of a C compiler and is directly executed by the x86 emulator.

The halt decider Halts() determines that H_Hat() called it in infinite 
recursion, on the basis of the x86 machine language execution trace 
shown below, stop simulating its input, and decide not halting on the 
basis that its input would not halt.

void H_Hat(u32 P)
{
   u32 Input_Would_Halt = Halts(P, P);
   if (Input_Would_Halt)
     HERE: goto HERE;
}


int main()
{
   u32 Input_Would_Halt = Halts((u32)H_Hat, (u32)H_Hat);
   Output("Input_Would_Halt = ", Input_Would_Halt);
}

_H_Hat()
[0000088f](01)  55              push ebp
[00000890](02)  8bec            mov ebp,esp
[00000892](01)  51              push ecx
[00000893](03)  8b4508          mov eax,[ebp+08]
[00000896](01)  50              push eax
[00000897](03)  8b4d08          mov ecx,[ebp+08]
[0000089a](01)  51              push ecx
[0000089b](05)  e87ffeffff      call 0000071f
[000008a0](03)  83c408          add esp,+08
[000008a3](03)  8945fc          mov [ebp-04],eax
[000008a6](04)  837dfc00        cmp dword [ebp-04],+00
[000008aa](02)  7402            jz 000008ae
[000008ac](02)  ebfe            jmp 000008ac
[000008ae](02)  8be5            mov esp,ebp
[000008b0](01)  5d              pop ebp
[000008b1](01)  c3              ret

_main()
[000008bf](01)  55              push ebp
[000008c0](02)  8bec            mov ebp,esp
[000008c2](01)  51              push ecx
[000008c3](05)  688f080000      push 0000088f
[000008c8](05)  688f080000      push 0000088f
[000008cd](05)  e84dfeffff      call 0000071f
[000008d2](03)  83c408          add esp,+08
[000008d5](03)  8945fc          mov [ebp-04],eax
[000008d8](03)  8b45fc          mov eax,[ebp-04]
[000008db](01)  50              push eax
[000008dc](05)  680b030000      push 0000030b
[000008e1](05)  e869faffff      call 0000034f
[000008e6](03)  83c408          add esp,+08
[000008e9](02)  33c0            xor eax,eax
[000008eb](02)  8be5            mov esp,ebp
[000008ed](01)  5d              pop ebp
[000008ee](01)  c3              ret

Columns
(1) Execution trace sequence number
(2) Machine address of instruction
(3) Machine address of top of stack
(4) Value of top of stack after instruction executed
(5) Number of bytes of machine code
(6) Machine language bytes
(7) Assembly language text

(01)[000008bf][00011208][00000000](01)  55              push ebp
(02)[000008c0][00011208][00000000](02)  8bec            mov ebp,esp
(03)[000008c2][00011204][00000000](01)  51              push ecx
(04)[000008c3][00011200][0000088f](05)  688f080000      push 0000088f
(05)[000008c8][000111fc][0000088f](05)  688f080000      push 0000088f
(06)[000008cd][000111f8][000008d2](05)  e84dfeffff      call 0000071f

(07)[0000088f][00031288][0003128c](01)  55              push ebp
(08)[00000890][00031288][0003128c](02)  8bec            mov ebp,esp
(09)[00000892][00031284][00021258](01)  51              push ecx
(10)[00000893][00031284][00021258](03)  8b4508          mov eax,[ebp+08]
(11)[00000896][00031280][0000088f](01)  50              push eax
(12)[00000897][00031280][0000088f](03)  8b4d08          mov ecx,[ebp+08]
(13)[0000089a][0003127c][0000088f](01)  51              push ecx
(14)[0000089b][00031278][000008a0](05)  e87ffeffff      call 0000071f

Line(11) Push second parameter value: 0000088f to Halts()
Line(13) Push first  parameter value: 0000088f to Halts()
Line(14) H_Halt() calls Halts(0000088f, 0000088f)

(15)[0000088f][00042430][00042434](01)  55              push ebp
(16)[00000890][00042430][00042434](02)  8bec            mov ebp,esp
(17)[00000892][0004242c][00032400](01)  51              push ecx
(18)[00000893][0004242c][00032400](03)  8b4508          mov eax,[ebp+08]
(19)[00000896][00042428][0000088f](01)  50              push eax
(20)[00000897][00042428][0000088f](03)  8b4d08          mov ecx,[ebp+08]
(21)[0000089a][00042424][0000088f](01)  51              push ecx
(22)[0000089b][00042420][000008a0](05)  e87ffeffff      call 0000071f

Line(19) Push second parameter value: 0000088f to Halts()
Line(21) Push first  parameter value: 0000088f to Halts()
Line(22) H_Halt() calls Halts(0000088f, 0000088f)

Infinite Recursion Detected Simulation Stopped on the basis that H_Hat() 
calls Halts() with the same data a second time in sequence from the same 
machine address.

(23)[000008d2][00011204][00000000](03)  83c408          add esp,+08
(24)[000008d5][00011204][00000000](03)  8945fc          mov [ebp-04],eax
(25)[000008d8][00011204][00000000](03)  8b45fc          mov eax,[ebp-04]
(26)[000008db][00011200][00000000](01)  50              push eax
(27)[000008dc][000111fc][0000030b](05)  680b030000      push 0000030b
(28)[000008e1][000111f8][000008e6](05)  e869faffff      call 0000034f
Input_Would_Halt = 0

(29)[000008e6][00011204][00000000](03)  83c408          add esp,+08
(30)[000008e9][00011204][00000000](02)  33c0            xor eax,eax
(31)[000008eb][00011208][00000000](02)  8be5            mov esp,ebp
(32)[000008ed][0001120c][00010000](01)  5d              pop ebp
(33)[000008ee][00011210][00000080](01)  c3              ret
Number_of_User_Instructions(33)

Copyright 2021 PL Olcott

[1] sci.logic --- Daryl McCullough --- Jun 25, 2004, 6:30:39 PM
[The Psychology of Self-Reference]
https://groups.google.com/g/sci.logic/c/4kIXI1kxmsI/m/hRroMoQZx2IJ



http://www.liarparadox.org/Eliminating_pathological_self_reference_error_from_the_halting_problem.pdf

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [standalone]


Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.software-eng


csiph-web