• Re: Concise refutation of halting problem proofs V27 [ input is not in

    From olcott@21:1/5 to All on Tue Nov 23 21:24:52 2021
    XPost: comp.theory, sci.logic, sci.math

    On 11/23/2021 8:22 PM, André G. Isaak wrote:
    On 2021-11-23 18:53, olcott wrote:
    On 11/23/2021 7:34 PM, André G. Isaak wrote:

    Crucially, the halting function exists *independently* and *prior* to
    any Turing Machine which attempts to compute this function. The halting function is *not* associated with any sort of algorithm; it is simply a mapping. In other words it is simply a denumerably infinite list of all possible computations and their halting status expressed as ordered pairs.



    You don't realize it but you are asking a decider to make its decision
    on the basis of a hypothetical string that does not actually exist.

    int H(ptr x, ptr y) { x(y); }
    int P(ptr x) { H(x, x); }
    int H1(ptr x, ptr y) { x(y); }

    The input to H requires that P call this very same H.
    The input to H1 has no such pathological relationship to P.

    By simply ignoring the pathological relationship between H and P you are answering the wrong question.

    You are answering the question:
    What would the behavior of P be if P called H1 instead of calling H?

    That makes the "input" to H hypothetical rather than an actual string.

    The computation P(P) will occur in this list exactly once, as will be
    true for all other computation. Since your P(P) halts, it will map to 'halts'.

    A halt decider, given <P> <P> as its input, is tasked with determining
    what the entry for that computation in the list described above actually
    is in a finite number of steps. If <P> <P> maps to 'halts' in the
    halting function, then a halt decider must accept it. If it maps to
    'doesn't halt', it must reject it.

    That means that the halting value of P(P) is *not* specific to a given
    halt decider. Your H and H1 must both provide the same answer if they
    are both halt deciders. It means that it is non-sensical to talk about
    the halting value of P(P) 'inside' some H, since H's job is to determine
    what value this computation maps to in the halting FUNCTION which is independent of any halt decider.

    André



    --
    Copyright 2021 Pete Olcott

    Talent hits a target no one else can hit;
    Genius hits a target no one else can see.
    Arthur Schopenhauer

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to All on Wed Nov 24 22:54:41 2021
    XPost: comp.theory, sci.logic, sci.math

    On 11/24/2021 9:50 AM, André G. Isaak wrote:
    On 2021-11-24 08:02, olcott wrote:
    On 11/24/2021 12:27 AM, André G. Isaak wrote:
    On 2021-11-23 22:48, olcott wrote:
    On 11/23/2021 10:18 PM, André G. Isaak wrote:
    On 2021-11-23 21:03, olcott wrote:
    On 11/23/2021 9:44 PM, André G. Isaak wrote:
    On 2021-11-23 20:24, olcott wrote:
    On 11/23/2021 8:22 PM, André G. Isaak wrote:
    On 2021-11-23 18:53, olcott wrote:
    On 11/23/2021 7:34 PM, André G. Isaak wrote:

    Crucially, the halting function exists *independently* and
    *prior* to any Turing Machine which attempts to compute this >>>>>>>>> function. The halting function is *not* associated with any
    sort of algorithm; it is simply a mapping. In other words it is >>>>>>>>> simply a denumerably infinite list of all possible computations >>>>>>>>> and their halting status expressed as ordered pairs.



    You don't realize it but you are asking a decider to make its
    decision on the basis of a hypothetical string that does not
    actually exist.

    ???

    So now you claim the STRING <P> <P> can't exist? But at the same >>>>>>> time you claim that your H1 returns the correct answer for this
    allegedly impossible string? How on earth does that work.


    int H(ptr x, ptr y) { x(y); }
    int H1(ptr x, ptr y) { x(y); int P(ptr x) { H(x, x); }
    int P1(ptr x) { H1(x, x); }


    What does any of this have to do with your ridiculous claim that
    the string <P> <P> does not actually exist?

    If you want the actual behavior of P(P) run independently
    then you have to change P or H into something that they are not
    because they are defined with hardwired inter-dependency.

    If you want the actual behaviour of P(P) run independently, you
    simply run P(P) independently.


    So in other words H must report on the behavior of a finite string
    that is not is input.

    H doesn't report on the behaviour of finite strings at all. It reports
    on the behaviour of computations.

    P(P) is a computation which halts.

    Your H needs to be able to report that P(P) halts (or any other
    arbitrary computation).

    Determining exactly how that particular computation must be encoded as a finite string so it can be passed as an input to H is part of your job
    when designing H.

    Maybe you don't grasp this. Consider two UTMs, X and Y (and by UTM I
    mean actual UTMs). Both of these should be able to emulate P(P) if we
    give them two copies of a string which describes the Turing Machine P.

    But the strings we pass to X and the string we pass to Y are *not* necessarily the same string. X and Y may use different alphabets and may
    use different encoding schemes. To constitute a UTM, it must be the
    case, though, that it is possible to represent every possible
    computation as a string that can be passed to that UTM.

    If you've designed an H such that there is no possible way to represent
    the independent computation P(P) as a string which can be passed to H as
    an input, then there is something wrong with your design.

    I think what you mean to say is if you want H to give you the correct
    answer about the actual behaviour of P(P) run independently, which it
    can't. The interdependency prevents this.


    It is incorrect to think of H having the hypothetical input where P
    does not call H.All deciders must have finite string inputs. Because P
    foes

    Where did I (or anyone) mention a P that does not simulate/call H?

    H is required to describe the halting behaviour of the independent computation P(P). That means it must describe how P(P) behaves when
    called directly from main rather than from within your halt decider.

    call this same H changing P so that it does not call this same H is
    incorrect.

    It is equally incorrect to have H report on the behavior of P as if H
    was H1 where P does not call H1.

    But that does not change the fact that the computation P(P) halts, and

    The fact there there are no cats in the kitchen does not have one damn
    thing to do with dogs in the living room. I can't imagine how people
    can so persistently make this strawman error even after being warned
    dozens of times.

    #include <stdint.h>
    #include <stdio.h>
    typedef int (*ptr)();

    int H(ptr x, ptr y)
    {
       x(y); // direct execution of P(P)
       return 1;
    }

    // Minimal essence of Linz(1990) Ĥ
    // and Strachey(1965) P
    int P(ptr x)
    {
       H(x, x);
       return 1; // Give P a last instruction at the "c" level
    }

    int main(void)
    {
       H(P, P);
    }

    Combinations of (H,P) having pathological self-reference (PSR)
       H(P,P) simulates or executes its input and aborts or does
       not abort its input and P(P) calls this same H(P,P) with itself.

    for all Hn(Pn,Pn) in the above PSR set Pn never reaches its final
    instruction.


    that this therefore is the only correct answer to the question which
    a halt decider is required to answer.

    That is not the freaking way that deciders work.

    A decider accepts or rejects all possible inputs based on some criteria determined by the problem at hand.

    For the halting problem, the criterion is that the decider must accept
    all and only those independent computations which HALT.


    If H(P,P) reports on the behavior of H1(P,P) or H(P1,P1) it freaking
    answered the wrong freaking question.

    Those are the only pair of combinations that show P(P) as an
    independent computation and they are both answers to the wrong question.

    NEITHER of those show P(P) as an independent computation.

    H(P,P) must report on the behaviour of P(P). That's the *only* behaviour
    it is being asked about.


    The one key verified fact that everyone simply assumes away even
    though it is a verified fact is that there are elements of the PSR set
    such that the input to Hn(Pn,Pn) never reaches its final state and
    Pn(Pn) does reach its final state in this exact same sequence of
    configurations.

    People assume that the placement in the execution trace can't make a
    difference and yet it is a verified fact that this placement does make
    a difference. The one way dependency relationship that Pn(Pn) has on
    Hn(Pn,Pn) causes the outer Pn to behave differently than the inner Pn.

    Simply assuming this away is flat out dishonest.

    None of this is relevant (or even coherent). H(P, P) by the definition
    of the problem must report the behaviour of the independent computation
    P(P). Whether the "placement in the execution trace can make a
    difference" has no bearing on the behaviour of P(P). It might have some bearing on the behaviour of the simulation of P(P) inside of H, but
    that's not what the halt decider is being asked about.

    The sequence of 1 to N configurations specified by the input to H(X, Y)
    cannot be correctly construed as anything other than the sequence of 1
    to N steps of the (direct execution, x86 emulation or UTM simulation of
    this input by H.



    --
    Copyright 2021 Pete Olcott

    Talent hits a target no one else can hit;
    Genius hits a target no one else can see.
    Arthur Schopenhauer

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