• Software engineers [ not Flibble ] can verify this halting problem proo

    From olcott@21:1/5 to Mr Flibble on Thu Jun 23 14:56:26 2022
    XPost: comp.theory, sci.logic, sci.math

    On 6/23/2022 2:41 PM, Mr Flibble wrote:
    On Thu, 23 Jun 2022 00:19:23 -0500
    olcott <NoOne@NoWhere.com> wrote:

    On 6/23/2022 12:13 AM, olcott wrote:
    On 6/22/2022 10:41 PM, Richard Damon wrote:
    On 6/22/22 10:55 PM, olcott wrote:
    On 6/22/2022 9:34 PM, Richard Damon wrote:
    On 6/22/22 10:18 PM, olcott wrote:
    On 6/22/2022 8:45 PM, Richard Damon wrote:
    On 6/22/22 9:41 PM, olcott wrote:
    On 6/22/2022 8:36 PM, Richard Damon wrote:
    On 6/22/22 9:29 PM, olcott wrote:
    On 6/22/2022 8:14 PM, Richard Damon wrote:
    On 6/22/22 8:55 PM, olcott wrote:
    On 6/22/2022 7:48 PM, Richard Damon wrote:
    On 6/22/22 8:37 PM, olcott wrote:

    First you agree that my words are perfectly correct >>>>>>>>>>>>>>> within their specified context

    Since you haven't actualy defined you context, and imply >>>>>>>>>>>>>> that it is the halting problem, where they can not be >>>>>>>>>>>>>> correct, that is not possible.

    First you agree that these words are 100% correct within >>>>>>>>>>>>> the context of software engineering totally ignoring the >>>>>>>>>>>>> context of the halting problem.

    #include <stdint.h>
    #define u32 uint32_t

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

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

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

    _P()
    [000010d2](01)  55              push ebp >>>>>>>>>>>>> [000010d3](02)  8bec            mov ebp,esp >>>>>>>>>>>>> [000010d5](03)  8b4508          mov eax,[ebp+08] >>>>>>>>>>>>> [000010d8](01)  50              push eax >>>>>>>>>>>>> [000010d9](03)  8b4d08          mov ecx,[ebp+08] >>>>>>>>>>>>> [000010dc](01)  51              push ecx >>>>>>>>>>>>> [000010dd](05)  e820feffff      call 00000f02
    [000010e2](03)  83c408          add esp,+08 >>>>>>>>>>>>> [000010e5](02)  85c0            test eax,eax >>>>>>>>>>>>> [000010e7](02)  7402            jz 000010eb >>>>>>>>>>>>> [000010e9](02)  ebfe            jmp 000010e9 >>>>>>>>>>>>> [000010eb](01)  5d              pop ebp >>>>>>>>>>>>> [000010ec](01)  c3              ret
    Size in bytes:(0027) [000010ec]

    Every sufficiently competent software engineer can easily >>>>>>>>>>>>> verify that the complete and correct x86 emulation of the >>>>>>>>>>>>> input to H(P,P) by H would never reach the "ret"
    instruction of P because both H and P would remain stuck >>>>>>>>>>>>> in infinitely recursive emulation.


    So, if H actually is a program that does a COMPLETE and >>>>>>>>>>>> correct x86 emulation of its input, then YES, as I have >>>>>>>>>>>> said many time before, this combination is non-halting. >>>>>>>>>>>>
    The fact that you need to keep going back to this, and >>>>>>>>>>>> seem to just be refusing to accept the conditions under >>>>>>>>>>>> which you have proved it just shows the problems with your >>>>>>>>>>>> thought process.
    If H does correctly determine that this is the case in a >>>>>>>>>>>>> finite number of steps then H could reject its input on >>>>>>>>>>>>> this basis. Here are the details of exactly how H does >>>>>>>>>>>>> this in a finite number of steps.

    Except that NOW H isn't the H we were just talking about, >>>>>>>>>>>> so you are just proving that you are either lying or an >>>>>>>>>>>> idiot.

    Remember, the first analysis had the CONDITION on it that >>>>>>>>>>>> H did a COMPLETE and correct x86 emulation.

    Once you remove that property form H, that conclusion no >>>>>>>>>>>> long holds and you are shown to be a lying idiot.


    typedef struct Decoded
    {
       u32 Address;
       u32 ESP;          // Current value of ESP >>>>>>>>>>>>>    u32 TOS;          // Current value of Top of Stack >>>>>>>>>>>>>    u32 NumBytes;
       u32 Simplified_Opcode;
       u32 Decode_Target;
    } Decoded_Line_Of_Code;

      machine   stack     stack     machine    assembly
      address   address   data      code       language
      ========  ========  ========  =========  ============= >>>>>>>>>>>>> [000010d2][00211e8a][00211e8e] 55         push ebp >>>>>>>>>>>>> [000010d3][00211e8a][00211e8e] 8bec       mov ebp,esp >>>>>>>>>>>>> [000010d5][00211e8a][00211e8e] 8b4508     mov eax,[ebp+08] >>>>>>>>>>>>> [000010d8][00211e86][000010d2] 50         push eax >>>>>>>>>>>>> // push P
    [000010d9][00211e86][000010d2] 8b4d08     mov ecx,[ebp+08] >>>>>>>>>>>>> [000010dc][00211e82][000010d2] 51         push ecx >>>>>>>>>>>>> // push P
    [000010dd][00211e7e][000010e2] e820feffff call 00000f02 >>>>>>>>>>>>> // call H
    Infinitely Recursive Simulation Detected Simulation
    Stopped

    // actual fully operational code in the x86utm operating >>>>>>>>>>>>> system u32 H(u32 P, u32 I)
    {
    HERE:
       u32 End_Of_Code;
       u32 Address_of_H;              // 2022-06-17 >>>>>>>>>>>>>    u32 code_end                  = get_code_end(P);
       Decoded_Line_Of_Code *decoded =
    (Decoded_Line_Of_Code*)
    Allocate(sizeof(Decoded_Line_Of_Code)); Registers*
    master_state      = (Registers*)
    Allocate(sizeof(Registers)); Registers*  slave_state >>>>>>>>>>>>> = (Registers*) Allocate(sizeof(Registers));
       u32*        slave_stack       = Allocate(0x10000); //
    64k; u32  execution_trace =
    (u32)Allocate(sizeof(Decoded_Line_Of_Code) * 1000);

       __asm lea eax, HERE             // 2022-06-18 >>>>>>>>>>>>>    __asm sub eax, 6                // 2022-06-18
       __asm mov Address_of_H, eax     // 2022-06-18 >>>>>>>>>>>>>    __asm mov eax, END_OF_CODE
       __asm mov End_Of_Code, eax

       Output("Address_of_H:", Address_of_H); // 2022-06-11 >>>>>>>>>>>>>    Init_slave_state(P, I, End_Of_Code, slave_state, >>>>>>>>>>>>> slave_stack);
       Output("\nBegin Simulation   Execution Trace Stored >>>>>>>>>>>>> at:", execution_trace);
       if (Decide_Halting(&execution_trace, &decoded, >>>>>>>>>>>>> code_end, &master_state,
                          &slave_state, &slave_stack,
    Address_of_H, P, I))
           goto END_OF_CODE;
       return 0;  // Does not halt
    END_OF_CODE:
       return 1; // Input has normally terminated
    }

    H knows its own machine address and on this basis it can >>>>>>>>>>>>> easily examine its stored execution_trace of P and
    determine: (a) P is calling H with the same arguments >>>>>>>>>>>>> that H was called with.
    (b) No instructions in P could possibly escape this
    otherwise infinitely recursive emulation.
    (c) H aborts its emulation of P before its call to H is >>>>>>>>>>>>> invoked.



    (b) is NOT a correct rule. Thos has been pointed out
    before, and you have ignored it.

    That you don't understand what I mean does not mean that it >>>>>>>>>>> is an incorrect rule.

    Here is an example where P does have instruction that could >>>>>>>>>>> possibly escape this otherwise infinitely recursive
    emulation:


    void P(ptr x)
    {
    static count = 0;
       count++;
       if count > 3)
         return;
       if (H(x, x))
         HERE: goto HERE;
       return;
    }


    FALLACY of proof by example. I never said that (b) isn't
    sometimes true, just it isn't an always true condition. You >>>>>>>>>> fail at elementary logic.

    Try and find a valid counter-example. Every attempt at
    rebuttal that is not a valid counter-example is one form of
    deception or another.



    P(P)

    That is not any example of (b), thus another mere strawman
    deception.

    Why not?

    It is not an example of the simulation of the input to H(P,P) at
    all.



    Why is P not P?


    It is not a direct rebuttal of my original claim.

    This would be a direct rebuttal:
    You must adapt P so that when H(P,P) emulates its input it
    determines that P never reaches its "ret" instruction and the
    adapted emulated P still reaches its "ret" instruction.


    Unless you find that at least one input where it gets the wrong
    answer you have not refuted me.

    Here:

    void Px(u32 x)
    {
    H(x, x);
    return;
    }

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

    ...[000013e8][00102357][00000000] 83c408 add esp,+08 ...[000013eb][00102353][00000000] 50 push eax ...[000013ec][0010234f][00000427] 6827040000 push 00000427 ---[000013f1][0010234f][00000427] e880f0ffff call 00000476
    Input_Halts = 0
    ...[000013f6][00102357][00000000] 83c408 add esp,+08 ...[000013f9][00102357][00000000] 33c0 xor eax,eax ...[000013fb][0010235b][00100000] 5d pop ebp ...[000013fc][0010235f][00000004] c3 ret
    Number of Instructions Executed(16120)

    It gets the answer wrong, i.e. input has not been decided correctly.
    QED.

    /Flibble



    To fully understand this code a software engineer must be an expert in:
    the C programming language, the x86 programming language, exactly how C translates into x86 and the ability to recognize infinite recursion at
    the x86 assembly language level. No knowledge of the halting problem is required.

    The ordinary semantics of standard C and the conventional x86 language
    are the entire semantics required to conclusively prove that H(Px,Px)
    does correctly determine that its correct and complete x86 emulation of
    its input would never reach the "ret" instruction of Px.

    It is always the case that whenever anyone disagrees with verifiable
    facts (as you have just done) that they are necessarily always incorrect.

    --
    Copyright 2022 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 Mr Flibble@21:1/5 to olcott on Thu Jun 23 20:59:44 2022
    XPost: comp.theory, sci.logic, sci.math

    On Thu, 23 Jun 2022 14:56:26 -0500
    olcott <NoOne@NoWhere.com> wrote:

    On 6/23/2022 2:41 PM, Mr Flibble wrote:
    On Thu, 23 Jun 2022 00:19:23 -0500
    olcott <NoOne@NoWhere.com> wrote:

    On 6/23/2022 12:13 AM, olcott wrote:
    On 6/22/2022 10:41 PM, Richard Damon wrote:
    On 6/22/22 10:55 PM, olcott wrote:
    On 6/22/2022 9:34 PM, Richard Damon wrote:
    On 6/22/22 10:18 PM, olcott wrote:
    On 6/22/2022 8:45 PM, Richard Damon wrote:
    On 6/22/22 9:41 PM, olcott wrote:
    On 6/22/2022 8:36 PM, Richard Damon wrote:
    On 6/22/22 9:29 PM, olcott wrote:
    On 6/22/2022 8:14 PM, Richard Damon wrote:
    On 6/22/22 8:55 PM, olcott wrote:
    On 6/22/2022 7:48 PM, Richard Damon wrote:
    On 6/22/22 8:37 PM, olcott wrote:

    First you agree that my words are perfectly correct >>>>>>>>>>>>>>> within their specified context

    Since you haven't actualy defined you context, and >>>>>>>>>>>>>> imply that it is the halting problem, where they can >>>>>>>>>>>>>> not be correct, that is not possible.

    First you agree that these words are 100% correct within >>>>>>>>>>>>> the context of software engineering totally ignoring the >>>>>>>>>>>>> context of the halting problem.

    #include <stdint.h>
    #define u32 uint32_t

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

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

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

    _P()
    [000010d2](01)  55              push ebp
    [000010d3](02)  8bec            mov ebp,esp
    [000010d5](03)  8b4508          mov eax,[ebp+08]
    [000010d8](01)  50              push eax
    [000010d9](03)  8b4d08          mov ecx,[ebp+08]
    [000010dc](01)  51              push ecx
    [000010dd](05)  e820feffff      call 00000f02
    [000010e2](03)  83c408          add esp,+08
    [000010e5](02)  85c0            test eax,eax
    [000010e7](02)  7402            jz 000010eb
    [000010e9](02)  ebfe            jmp 000010e9
    [000010eb](01)  5d              pop ebp
    [000010ec](01)  c3              ret
    Size in bytes:(0027) [000010ec]

    Every sufficiently competent software engineer can >>>>>>>>>>>>> easily verify that the complete and correct x86
    emulation of the input to H(P,P) by H would never reach >>>>>>>>>>>>> the "ret" instruction of P because both H and P would >>>>>>>>>>>>> remain stuck in infinitely recursive emulation.


    So, if H actually is a program that does a COMPLETE and >>>>>>>>>>>> correct x86 emulation of its input, then YES, as I have >>>>>>>>>>>> said many time before, this combination is non-halting. >>>>>>>>>>>>
    The fact that you need to keep going back to this, and >>>>>>>>>>>> seem to just be refusing to accept the conditions under >>>>>>>>>>>> which you have proved it just shows the problems with >>>>>>>>>>>> your thought process.
    If H does correctly determine that this is the case in a >>>>>>>>>>>>> finite number of steps then H could reject its input on >>>>>>>>>>>>> this basis. Here are the details of exactly how H does >>>>>>>>>>>>> this in a finite number of steps.

    Except that NOW H isn't the H we were just talking about, >>>>>>>>>>>> so you are just proving that you are either lying or an >>>>>>>>>>>> idiot.

    Remember, the first analysis had the CONDITION on it that >>>>>>>>>>>> H did a COMPLETE and correct x86 emulation.

    Once you remove that property form H, that conclusion no >>>>>>>>>>>> long holds and you are shown to be a lying idiot.


    typedef struct Decoded
    {
       u32 Address;
       u32 ESP;          // Current value of ESP
       u32 TOS;          // Current value of Top of Stack >>>>>>>>>>>>>    u32 NumBytes;
       u32 Simplified_Opcode;
       u32 Decode_Target;
    } Decoded_Line_Of_Code;

      machine   stack     stack     machine    assembly >>>>>>>>>>>>>   address   address   data      code       language >>>>>>>>>>>>>   ========  ========  ========  =========
    ============= [000010d2][00211e8a][00211e8e] 55
    push ebp [000010d3][00211e8a][00211e8e] 8bec       mov >>>>>>>>>>>>> ebp,esp [000010d5][00211e8a][00211e8e] 8b4508     mov >>>>>>>>>>>>> eax,[ebp+08] [000010d8][00211e86][000010d2] 50
    push eax // push P
    [000010d9][00211e86][000010d2] 8b4d08     mov
    ecx,[ebp+08] [000010dc][00211e82][000010d2] 51
    push ecx // push P
    [000010dd][00211e7e][000010e2] e820feffff call 00000f02 >>>>>>>>>>>>> // call H
    Infinitely Recursive Simulation Detected Simulation >>>>>>>>>>>>> Stopped

    // actual fully operational code in the x86utm operating >>>>>>>>>>>>> system u32 H(u32 P, u32 I)
    {
    HERE:
       u32 End_Of_Code;
       u32 Address_of_H;              // 2022-06-17
       u32 code_end                  = get_code_end(P); >>>>>>>>>>>>>    Decoded_Line_Of_Code *decoded =
    (Decoded_Line_Of_Code*)
    Allocate(sizeof(Decoded_Line_Of_Code)); Registers* >>>>>>>>>>>>> master_state      = (Registers*)
    Allocate(sizeof(Registers)); Registers*  slave_state >>>>>>>>>>>>> = (Registers*) Allocate(sizeof(Registers));
       u32*        slave_stack       = Allocate(0x10000); >>>>>>>>>>>>> // 64k; u32  execution_trace =
    (u32)Allocate(sizeof(Decoded_Line_Of_Code) * 1000); >>>>>>>>>>>>>
       __asm lea eax, HERE             // 2022-06-18
       __asm sub eax, 6                // 2022-06-18
       __asm mov Address_of_H, eax     // 2022-06-18
       __asm mov eax, END_OF_CODE
       __asm mov End_Of_Code, eax

       Output("Address_of_H:", Address_of_H); // 2022-06-11 >>>>>>>>>>>>>    Init_slave_state(P, I, End_Of_Code, slave_state, >>>>>>>>>>>>> slave_stack);
       Output("\nBegin Simulation   Execution Trace Stored >>>>>>>>>>>>> at:", execution_trace);
       if (Decide_Halting(&execution_trace, &decoded, >>>>>>>>>>>>> code_end, &master_state,
                          &slave_state, &slave_stack, >>>>>>>>>>>>> Address_of_H, P, I))
           goto END_OF_CODE;
       return 0;  // Does not halt
    END_OF_CODE:
       return 1; // Input has normally terminated
    }

    H knows its own machine address and on this basis it can >>>>>>>>>>>>> easily examine its stored execution_trace of P and >>>>>>>>>>>>> determine: (a) P is calling H with the same arguments >>>>>>>>>>>>> that H was called with.
    (b) No instructions in P could possibly escape this >>>>>>>>>>>>> otherwise infinitely recursive emulation.
    (c) H aborts its emulation of P before its call to H is >>>>>>>>>>>>> invoked.



    (b) is NOT a correct rule. Thos has been pointed out >>>>>>>>>>>> before, and you have ignored it.

    That you don't understand what I mean does not mean that >>>>>>>>>>> it is an incorrect rule.

    Here is an example where P does have instruction that
    could possibly escape this otherwise infinitely recursive >>>>>>>>>>> emulation:


    void P(ptr x)
    {
    static count = 0;
       count++;
       if count > 3)
         return;
       if (H(x, x))
         HERE: goto HERE;
       return;
    }


    FALLACY of proof by example. I never said that (b) isn't >>>>>>>>>> sometimes true, just it isn't an always true condition. You >>>>>>>>>> fail at elementary logic.

    Try and find a valid counter-example. Every attempt at
    rebuttal that is not a valid counter-example is one form of >>>>>>>>> deception or another.



    P(P)

    That is not any example of (b), thus another mere strawman
    deception.

    Why not?

    It is not an example of the simulation of the input to H(P,P) at
    all.



    Why is P not P?


    It is not a direct rebuttal of my original claim.

    This would be a direct rebuttal:
    You must adapt P so that when H(P,P) emulates its input it
    determines that P never reaches its "ret" instruction and the
    adapted emulated P still reaches its "ret" instruction.


    Unless you find that at least one input where it gets the wrong
    answer you have not refuted me.

    Here:

    void Px(u32 x)
    {
    H(x, x);
    return;
    }

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

    ...[000013e8][00102357][00000000] 83c408 add esp,+08 ...[000013eb][00102353][00000000] 50 push eax ...[000013ec][0010234f][00000427] 6827040000 push 00000427 ---[000013f1][0010234f][00000427] e880f0ffff call 00000476
    Input_Halts = 0
    ...[000013f6][00102357][00000000] 83c408 add esp,+08 ...[000013f9][00102357][00000000] 33c0 xor eax,eax ...[000013fb][0010235b][00100000] 5d pop ebp ...[000013fc][0010235f][00000004] c3 ret
    Number of Instructions Executed(16120)

    It gets the answer wrong, i.e. input has not been decided correctly.
    QED.

    /Flibble



    To fully understand this code a software engineer must be an expert
    in: the C programming language, the x86 programming language, exactly
    how C translates into x86 and the ability to recognize infinite
    recursion at the x86 assembly language level. No knowledge of the
    halting problem is required.

    The ordinary semantics of standard C and the conventional x86
    language are the entire semantics required to conclusively prove that H(Px,Px) does correctly determine that its correct and complete x86
    emulation of its input would never reach the "ret" instruction of Px.

    It is always the case that whenever anyone disagrees with verifiable
    facts (as you have just done) that they are necessarily always
    incorrect.

    Nope. You are incorrect and your H is incorrect: Px should always halt
    if H is a valid halt decider that returns to its invoker: Px (i.e. not
    main).

    /Flibble

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