XPost: comp.theory, sci.logic, sci.math

On 9/19/2021 4:30 AM, Malcolm McLean wrote:

On Sunday, 19 September 2021 at 04:42:41 UTC+1, olcott wrote:

This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:

As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of
{1,0} (indicating true or false) from this function, then whatever
occurs in-between does not make any difference.

This would mean that my use of static local variables has no detrimental
effect on the applicability of my partial halt decider to the halting
problem.

u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;

To qualify as a decider, the halt decider must calculate a (mathematical) function.
That is, for each possible input, there must be one and only one output, that is always the same for each input.

How a piece of computer code achieves that is not important, and details vary from language to language. In some primitive languages (or high-level scripting
languages) it may not be possible to declare local variables, for instance.

That is great. If this truly is the case then this completes the essence
of my system.

This enables a decidability decider that refutes Rice's theorem:

u32 PSR_Olcott_2004(u32 P)
{
return H1(P,P) != H(P,P);
}

int main()
{
Output("Pathological Self-Reference(Olcott 2004) = ",
PSR_Olcott_2004((u32) P));
}

--
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, sci.logic, sci.math

On 9/20/2021 11:15 AM, Charlie-Boo wrote:

On Saturday, September 18, 2021 at 11:42:41 PM UTC-4, olcott wrote:

This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:

As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of
{1,0} (indicating true or false) from this function, then whatever
occurs in-between does not make any difference.

This would mean that my use of static local variables has no detrimental
effect on the applicability of my partial halt decider to the halting
problem.

u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;



--
Copyright 2021 Pete Olcott

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

There is no significance to solving "some instances" of a problem. That includes no instances or trivial instances (here it would be YES answers) which have no significance.
It's basically impossible to carve out any non-trivial subsets of programs whose halting problem can be solved.
The easiest way to advance unsolvable problems (nonrecursive sets) has always been to find unsolved problems - proving sets are not recursive, typically r.e. sets.
C-B

void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

int main()
{
Output("Input_Halts = ", H1((u32)P, (u32)P));
}

H and H1 are simulating partial halt deciders that make their halt
status decision on the basis of whether or not the execution trace of
the simulation of their input matches one of two known infinite
execution patterns.

The above conventional undecidable TM/input pair is correctly decided as halting on the basis of fully operational C/x86 code in the x86utm
operating system.

H1 is an exact copy of H and is able to correctly decide that its input
halts because P was not designed to contradict H1. Because P was
intentionally designed to contradict H the return value from H and H1
are not the same.

The key question of this post is whether H/H1 would be disallowed as
Turing computable on the basis that H must use static local variables to
keep track of the execution trace of its input across subsequent
recursive simulations. If it used non-static locals the stored execution
trace of H would keep getting erased on every recursive simulation.
Since H1 is only called once this is not an issue for H1.

The initial input to H1/H and the final output from H1/H are always the
same for the same initial inputs.

--
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, sci.logic, sci.math

On 9/20/2021 12:17 PM, André G. Isaak wrote:

On 2021-09-20 10:44, olcott wrote:

On 9/20/2021 11:15 AM, Charlie-Boo wrote:

On Saturday, September 18, 2021 at 11:42:41 PM UTC-4, olcott wrote:

This is my paraphrase of the requirement a partial
halt decider must be a pure function of its inputs:

As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of
{1,0} (indicating true or false) from this function, then whatever
occurs in-between does not make any difference.

This would mean that my use of static local variables has no
detrimental
effect on the applicability of my partial halt decider to the halting
problem.

u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;



--
Copyright 2021 Pete Olcott

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

There is no significance to solving "some instances" of a problem.
That includes no instances or trivial instances (here it would be YES
answers) which have no significance.
It's basically impossible to carve out any non-trivial subsets of
programs whose halting problem can be solved.
The easiest way to advance unsolvable problems (nonrecursive sets)
has always been to find unsolved problems - proving sets are not
recursive, typically r.e. sets.
C-B

void P(u32 x)
{
   if (H(x, x))
     HERE: goto HERE;
}

int main()
{
   Output("Input_Halts = ", H1((u32)P, (u32)P));
}

H and H1 are simulating partial halt deciders that make their halt
status decision on the basis of whether or not the execution trace of
the simulation of their input matches one of two known infinite
execution patterns.

The above conventional undecidable TM/input pair is correctly decided
as halting on the basis of fully operational C/x86 code in the x86utm
operating system.

Your P is derived from H (somewhat) in accordance with the rules that
Linz uses to derive H_Hat from H.

Your P is *not* derived from H1 in this way.

If your H1 can correctly decide (P, P) that has no bearing on Linz.

It may seem that way to a reviewer that says blah, blah, blah, I know
that you must be wrong because I really, really believe that you must be
wrong so there is no sense in paying any attention to what you say.

On the other hand Olcott H1/H/P is analogous to Linz H/Ĥ/⟨Ĥ⟩ in that it shows that simulating halt decider Linz H correctly decides the halt
status of the Linz input ⟨Ĥ⟩ ⟨Ĥ⟩.

Linz
never claimed that you cannot construct a TM which correctly decides
H_Hat, H_Hat. He claims only that H cannot do so.

The whole point of the halting theorem is to prove that no universal
halt decider can possibly exist.

I have shown how to create a decidability decider that correctly decides
that Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ is not correctly decidable by Ĥ.qx, thus allowing H to
be automatically selected as the correct halting decider for ⟨Ĥ⟩ ⟨Ĥ⟩, thus the combination of the decidability decider and three instances of
the same algorithm derives a universal halt decider.

When H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ != When Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ we know that
⟨Ĥ⟩ ⟨Ĥ⟩ is not correctly decidable for either H or Ĥ.qx, one more instance of this same algorithm excludes the odd-man-out and thus
selects the correct halt decider.

Your H can *not* correctly decide (P, P) and that's the case that
actually matters.

H1 is an exact copy of H and is able to correctly decide that its
input halts because P was not designed to contradict H1. Because P was
intentionally designed to contradict H the return value from H and H1
are not the same.

The key question of this post is whether H/H1 would be disallowed as
Turing computable on the basis that H must use static local variables
to keep track of the execution trace of its input across subsequent
recursive simulations.

If it must keep track of *any* data across different calls then it is
not a computation. So yes, it is disqualified.

André

--
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, sci.logic, sci.math

On 9/20/2021 12:59 PM, André G. Isaak wrote:

On 2021-09-20 11:42, olcott wrote:

On 9/20/2021 12:17 PM, André G. Isaak wrote:

On 2021-09-20 10:44, olcott wrote:

On 9/20/2021 11:15 AM, Charlie-Boo wrote:

On Saturday, September 18, 2021 at 11:42:41 PM UTC-4, olcott wrote: >>>>>> This is my paraphrase of the requirement a partial

halt decider must be a pure function of its inputs:

As long as there is one set of inputs such as such as the formal
parameters to a function and a single output such as return value of >>>>>> {1,0} (indicating true or false) from this function, then whatever >>>>>> occurs in-between does not make any difference.

This would mean that my use of static local variables has no
detrimental
effect on the applicability of my partial halt decider to the halting >>>>>> problem.

u32 H(u32 P, u32 I)
{
static u32 Aborted;
static u32* execution_trace;



--
Copyright 2021 Pete Olcott

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

There is no significance to solving "some instances" of a problem.
That includes no instances or trivial instances (here it would be
YES answers) which have no significance.
It's basically impossible to carve out any non-trivial subsets of
programs whose halting problem can be solved.
The easiest way to advance unsolvable problems (nonrecursive sets)
has always been to find unsolved problems - proving sets are not
recursive, typically r.e. sets.
C-B

void P(u32 x)
{
   if (H(x, x))
     HERE: goto HERE;
}

int main()
{
   Output("Input_Halts = ", H1((u32)P, (u32)P));
}

H and H1 are simulating partial halt deciders that make their halt
status decision on the basis of whether or not the execution trace
of the simulation of their input matches one of two known infinite
execution patterns.

The above conventional undecidable TM/input pair is correctly
decided as halting on the basis of fully operational C/x86 code in
the x86utm operating system.

Your P is derived from H (somewhat) in accordance with the rules that
Linz uses to derive H_Hat from H.

Your P is *not* derived from H1 in this way.

If your H1 can correctly decide (P, P) that has no bearing on Linz.

It may seem that way to a reviewer that says blah, blah, blah, I know
that you must be wrong because I really, really believe that you must
be wrong so there is no sense in paying any attention to what you say.

It doesn't merely seem that way, it is that way.

On the other hand Olcott H1/H/P is analogous to Linz H/Ĥ/⟨Ĥ⟩ in that it

Given that your P is essentially Linz's H_Hat, How can H1/H/P be
analogous to H/Ĥ/⟨Ĥ⟩?

You're claiming that your H is somehow analogous to both Linz's H and to Linz's H_Hat.

You have to pay complete attention not merely glance at a couple of
words before forming your rebuttal.

Olcott H(P,P) is analogous to Linz Linz Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩
Olcott H1(P,P) is analogous to Linz Linz H ⟨Ĥ⟩ ⟨Ĥ⟩

shows that simulating halt decider Linz H correctly decides the halt
status of the Linz input ⟨Ĥ⟩ ⟨Ĥ⟩.

Linz never claimed that you cannot construct a TM which correctly
decides H_Hat, H_Hat. He claims only that H cannot do so.

The whole point of the halting theorem is to prove that no universal
halt decider can possibly exist.

I have shown how to create a decidability decider that correctly
decides that Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ is not correctly decidable by Ĥ.qx, thus
allowing H to be automatically selected as the correct halting decider
for ⟨Ĥ⟩ ⟨Ĥ⟩, thus the combination of the decidability decider and >> three instances of the same algorithm derives a universal halt decider.

When H applied to ⟨Ĥ⟩ ⟨Ĥ⟩ != When Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ we know that
⟨Ĥ⟩ ⟨Ĥ⟩ is not correctly decidable for either H or Ĥ.qx, one more >> instance of this same algorithm excludes the odd-man-out and thus
selects the correct halt decider.

But, as I have pointed out previously, and which you ignored, you are
then claiming that your *real* halt decider is the combination of H, H1,
Hx and your 'decidability decider'.

Yes.

In that case your P must be derived from that *combination* if you want
to claim that it is analogous to Linz's H_Hat.

No Olcott H1,H,Hx is superior to anything that Linz said because there
is no input that it cannot decide.

The whole point of the Linz proof is that for *any* 'halt decider' X,
one can always construct an X_Hat which it cannot decide correctly. Your combined H+H1+Hx+DD is just as susceptible to this as any other putative 'halt decider'.

André

The whole point of all these proofs is that no universal halt decider
exists. The Olcott combination of H1,H,Hx is such a universal halt
decider that is purported to not exist.

The key breakthrough is that Rice's theorem "proved" that no
decidability decider can possibly exist thus once we have such a
decidability decider Rice's theorem and the halting theorem both fail.



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