XPost: comp.theory

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.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory

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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)

XPost: comp.theory

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 <[email protected]> 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

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)