• Re: Concise refutation of halting problem proofs V5 [Linz version] (Fli

    From olcott@21:1/5 to Ben Bacarisse on Wed Nov 10 20:33:19 2021
    XPost: comp.theory, sci.logic, sci.math

    On 11/10/2021 8:08 PM, Ben Bacarisse wrote:
    Richard Damon <Richard@Damon-Family.org> writes:

    On 11/10/21 8:36 AM, Ben Bacarisse wrote:
    Richard Damon <Richard@Damon-Family.org> writes:

    On 11/10/21 6:35 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Here is the same thing using Peter Linz notation:
    Oh dear, back to talking about Turing machines...

    In this Linz machine:
    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
    it is true that the correct pure simulation of the
    input to Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩
    There is no string ⟨Ĥ⟩, so there is nothing that can be simulated. You
    keep removing the clause that defines Ĥ's behaviour:
    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn
    if (and only if) Ĥ applied to ⟨Ĥ⟩ does not halt.
    With that clause put back, you (well, other people at least) can see >>>>> that no TM can behave like this.

    But, if you step back a bit and ask about the H^ based on a machine H
    that CLAIMS to meet the requirements, then you can have a H^ and a
    <H^>.
    I disagree (though it's largely philosophical at this point). From the
    claim that H meets Linz's spec we can deduce all sort of things. One of >>> which is that there is no string <H^>. But can also deduce any other
    contradiction you like.
    And that's the trouble. Anything PO says about such an H^ is validly
    entailed by the assumption. He can even claim that 1 == 0 follows from
    "Linz's specs", and he'd be right. At some stage you have to point out
    the contradictions and force PO to abandon the initial assumption.

    I, for one, am fed up with trying to explain ever more silly
    consequences of the initial assumption about H. The proof is simple and >>> the contradiction entailed is obvious.

    The difference is that PO HAS an H, so H does exist, and we can thus
    build a H^ from. (This assumes we can convert is 'C Program' into some
    sort of Turing Machine).

    Not in this sub-thread. He starts: "In this Linz machine:" and then
    gives the line he say not yet understood. He calls everything H, but
    when it's Linz's we must assume what Linz assumes.

    When H refers to his code, it's wrong for the reasons you and André and
    I have been saying. If it's Linz H, it does not exist (or the class of
    TMs referred to by H is empty).

    Anyway, I'm butting out. If I've written out the proof using TMs more
    than once, and the world has told him that his C code is wrong by
    definition, but there is no way he will ever see any of this. It's not
    that he's stupid, it's just that he's invested a significant proportion
    of his life, and most of his self-esteem, in this ill thought out idea.
    The mind will play extraordinary tricks in that sort of situation.


    Within the definition of the x86 language H(P,P)==0 is a necessary
    consequence for every simulating halt decider H.

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

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

    _P()
    [00000c36](01) 55 push ebp
    [00000c37](02) 8bec mov ebp,esp
    [00000c39](03) 8b4508 mov eax,[ebp+08] // 2nd Param
    [00000c3c](01) 50 push eax
    [00000c3d](03) 8b4d08 mov ecx,[ebp+08] // 1st Param
    [00000c40](01) 51 push ecx
    [00000c41](05) e820fdffff call 00000966 // call H
    [00000c46](03) 83c408 add esp,+08
    [00000c49](02) 85c0 test eax,eax
    [00000c4b](02) 7402 jz 00000c4f
    [00000c4d](02) ebfe jmp 00000c4d
    [00000c4f](01) 5d pop ebp
    [00000c50](01) c3 ret
    Size in bytes:(0027) [00000c50]

    Within the definition of the x86 language H(P,P)==0 is a necessary
    consequence for every simulating halt decider H.


    Indeed. So tell PO that there is no string <H^>. If there were, there
    wold be a TM H^ halts if it does not and does not halt if it does.

    Except that you can create an machine H that you can (incorrectly)
    claim to meet the requirements, and thus a machine H^ can be created
    and thus the string <H^> exists.

    If he starts "my H" then yes, but he started "this Linz machine". Of
    course calling everything H is just another silly thing he does, but
    there is "Linz's H" which does not exist, and "his H" which does not
    meet Linz's specification.


    Everyone simply leaps to the conclusion that I must be wrong yet can't
    point to a single error in the actual inference steps that prove my
    point. Perhaps this simply means that everyone here is mostly clueless
    about the x86 language.

    Flibble seems to understand me quite well. He even understood the last
    required step to convert my H into a pure function so well that he
    presented it before I did.

    [Olcott wrong about infinite recursion] comp.theory
    On 11/10/2021 3:53 PM, Mr Flibble wrote:
    Olcott is barking up the wrong tree re infinite recursion: there
    is only a need to detect a single recursive call into the halt decider
    and signal an exception. Why? Because infinite recursion is valid
    program behavior.

    /Flibble




    Halting problem undecidability and infinitely nested simulation (V2)

    https://www.researchgate.net/publication/356105750_Halting_problem_undecidability_and_infinitely_nested_simulation_V2




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