XPost: comp.theory, comp.software-eng, sci.math.symbolic

On 8/31/2021 10:07 AM, André G. Isaak wrote:

On 2021-08-31 08:24, olcott wrote:

On 8/30/2021 11:45 PM, André G. Isaak wrote:

     In computability theory, the halting problem is the
    problem of determining, from a description of an
    arbitrary computer program and an input, whether the
    program will finish running, or continue to run forever.
    https://en.wikipedia.org/wiki/Halting_problem

The halting problem is always about program descriptions
not running programs. This means that it is always about
the input to the halt decider not the direct execution
of the program.

This is, of course, errant nonsense. The input to a halt decider is
simply data. Data doesn't *have* halting behaviour. Only the actual computation described by that data can have halting behaviour. Your
inability to comprehend simple definitions is not the basis for a
coherent argument.

The most straight forward way to get the actual behavior of a program
description is to simulate it.

No. The most straightforward way, and the ONLY 100% reliable way to get
the actual behaviour of a program description is to run the program it describes.

A pure simulation would have identical halting behaviour as the
actual computation, but the question isn't about simulations. It's
about actual computations. It isn't about what happens inside some
decider; it's about actual computations.

When an "actual computation" has different behavior than the
simulation of the input to the halt decider this proves that the
actual computation is a different computation than the input to the
halt decider thus not relevant to the halting problem.

No, it proves that the 'simulation' performed by your halt decider is
not an accurate simulation.

André

I think that I finally got it this time:

The difference in the relative invocation order of P(P) to H(P,P)
accounts for the difference in behavior.

P(P) from main() invokes P(P) then H(P,P).

H(P,P) from main reverses this relative invocation order to H(P,P) then
P(P).

Changes to the relative invocation order define distinctly different computations that can have different behavior without contradiction.


--
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, comp.software-eng, sci.math.symbolic

On 8/31/2021 4:17 PM, Malcolm McLean wrote:

On Tuesday, 31 August 2021 at 20:11:39 UTC+1, olcott wrote:

On 8/31/2021 1:40 PM, André G. Isaak wrote:

It makes no reference at all to the "relative invocation order" of H
with respect to P. It makes no reference to H at all.

If its answer doesn't correspond to the behaviour of P(P) which is a
halting computation, then its answer is *wrong*.

H(P,P) specifies the invocation order of H(P,P) then P(P).

If P did not have the pathological self-reference error the invocation
would not matter. Because P does have the pathological self-reference
error the invocation order does matter.

It is very diffcult to correctly handle incorrect input.

The key irrefutable point is that H(P,P) then P(P) is an entirely
different computation than P(P) then H(P,P)

So that's the central point. If H(P,P) from the root is a different computation
to H(P,P),called from P, then indeed you can provide a counter-example to
the Linz proof.

// Simplified Linz Ĥ (Linz:1990:319)
// Strachey(1965) CPL translated to C
void P(u32 x)
{
if (H(x, x))
HERE: goto HERE;
}

// These are two different computations that can have
// opposite results without contradiction.

int main () { H(P,P); } // invocation order H(P,P) then P(P)
int main () { P(P); } // invocation order P(P) then H(P,P)

H(P,P) from anywhere has exactly the same behavior.

// H1 is an identical copy of H
int main () { H1(P,P); } // reports that its input halts.

The different invocation order of H1 and H is how they can have
identical code and different behavior. Halt deciders can only see the instructions that they (and their slave instances) simulate. H1 cannot
see any of the instructions that H simulates.

H(P,P); P(P); and H1(P,P); are shown in sections V1,V2,V3 of this paper:

https://www.researchgate.net/publication/351947980_Halting_problem_undecidability_and_infinitely_nested_simulation

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