• How do we know H(P,P)==0 is the correct halt status for the input t

    From olcott@21:1/5 to olcott on Sat Aug 14 10:50:52 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/14/2021 10:17 AM, olcott wrote:
    This exact same analysis always applies to the input to H(P,P) no matter
    how it is called including this example:

    int main()
    {
      P((u32)P);
    }

       the Turing machine halting problem. Simply stated, the problem
       is: given the description of a Turing machine M and an input w,
       does M, when started in the initial configuration q0w, perform a
       computation that eventually halts? (Linz:1990:317).

       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

    Because the halting problem only requires that the (at least partial)
    halt decider decide its input correctly the fact that the direct
    invocation of P(P) is not an input to H, means that it is not relevant
    to the halting problem.

    The P(P) of main() only halts because H(P,P) correctly decides that its
    input never halts. This cause-and-effect relationship between the
    simulated P and the executed P proves that the simulated P and the
    executed P are distinctly different computations.

    Because they are different computations the fact that the executed P
    halts does not contradict the fact that the simulated P never halts.

    While H remains in pure simulation mode simulating the input to H(P,P)
    this simulated input never halts thus conclusively proving that H
    decides this input correctly.

    Because H only acts as a pure simulator of its input until after its
    halt status decision has been made it has no behavior that can possibly effect the behavior of its input. Because of this H screens out its own address range in every execution trace that it examines. This is why we
    never see any instructions of H in any execution trace after an input
    calls H.

    *Halting computation* is any computation that eventually reaches its own final state. This criteria divides computations that halt from those
    that merely stop running because their simulation was aborted.

      A Turing machine is said to halt whenever it reaches a configuration
      for which δ is not defined; this is possible because δ is a partial
      function. In fact, we will assume that no transitions are defined for
      any final state, so the Turing machine will halt whenever it enters a
      final state. (Linz:1990:234)

    // 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]

    _main()
    [00000c56](01)  55          push ebp
    [00000c57](02)  8bec        mov ebp,esp
    [00000c59](05)  68360c0000  push 00000c36    // push P
    [00000c5e](05)  68360c0000  push 00000c36    // push P
    [00000c63](05)  e8fefcffff  call 00000966    // call H(P,P) [00000c68](03)  83c408      add esp,+08
    [00000c6b](01)  50          push eax
    [00000c6c](05)  6857030000  push 00000357
    [00000c71](05)  e810f7ffff  call 00000386
    [00000c76](03)  83c408      add esp,+08
    [00000c79](02)  33c0        xor eax,eax
    [00000c7b](01)  5d          pop ebp
    [00000c7c](01)  c3          ret
    Size in bytes:(0039) [00000c7c]

     machine   stack     stack     machine    assembly
     address   address   data      code       language
     ========  ========  ========  =========  ============= [00000c56][0010172a][00000000] 55          push ebp [00000c57][0010172a][00000000] 8bec        mov ebp,esp [00000c59][00101726][00000c36] 68360c0000  push 00000c36 // push P [00000c5e][00101722][00000c36] 68360c0000  push 00000c36 // push P [00000c63][0010171e][00000c68] e8fefcffff  call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55          push ebp [00000c37][002117ca][002117ce] 8bec        mov ebp,esp [00000c39][002117ca][002117ce] 8b4508      mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50          push eax       // push P
    [00000c3d][002117c6][00000c36] 8b4d08      mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51          push ecx       // push P
    [00000c41][002117be][00000c46] e820fdffff  call 00000966  // call H(P,P)

    We can see that the first seven lines of P repeat. P calls H(P,P) that simulates P(P) that calls H(P,P) in a cycle the never stops unless H
    stops simulating its input. When H does stop simulating its input P
    never reaches its final state of [00000c50] therefore never halts even
    though it stops running.

    [00000c36][0025c1f2][0025c1f6] 55          push ebp [00000c37][0025c1f2][0025c1f6] 8bec        mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508      mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50          push eax       // push P
    [00000c3d][0025c1ee][00000c36] 8b4d08      mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51          push ecx       // push P
    [00000c41][0025c1e6][00000c46] e820fdffff  call 00000966  // call H(P,P) Local Halt Decider: Infinite Recursion Detected Simulation Stopped

    [00000c68][0010172a][00000000] 83c408      add esp,+08 [00000c6b][00101726][00000000] 50          push eax [00000c6c][00101722][00000357] 6857030000  push 00000357 [00000c71][00101722][00000357] e810f7ffff  call 00000386
    Input_Halts = 0
    [00000c76][0010172a][00000000] 83c408      add esp,+08 [00000c79][0010172a][00000000] 33c0        xor eax,eax [00000c7b][0010172e][00100000] 5d          pop ebp [00000c7c][00101732][00000068] c3          ret Number_of_User_Instructions(27)
    Number of Instructions Executed(23721)

    *Strachey, C 1965*  An impossible program The Computer Journal, Volume
    7, Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313

    *Linz, Peter 1990* An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.


    **test bolding**

    --
    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)
  • From olcott@21:1/5 to wij on Sat Aug 14 11:16:11 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/14/2021 11:05 AM, wij wrote:
    On Saturday, 14 August 2021 at 23:18:03 UTC+8, olcott wrote:
    This exact same analysis always applies to the input to H(P,P) no matter
    how it is called including this example:

    int main()
    {
    P((u32)P);
    }

    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    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

    Because the halting problem only requires that the (at least partial)
    halt decider decide its input correctly the fact that the direct
    invocation of P(P) is not an input to H, means that it is not relevant
    to the halting problem.

    I do not know English well, but I (almost every programmer) am sure the halting
    problem means a program H decides whether P(input) will halt or not.
    If the quoted texts is read to you differently, it is the problem of that texts.
    Submit message to the authors.


    The quoted texts are accurate. The (at least partial) halt decider must
    only correctly decide the halt status of its input. Computations that
    are not inputs to the halt decider do not pertain to the halting problem.

    If the direct invocation of P(P) is not relevant to the halting problem, then H can do whatever you like, therefore, meaningless if not garbage.


    The halting problem is only concerned with an at least partial halt
    decider correctly deciding whether or not its input halts, thus it can
    do whatever its wants as long as it does decide the correct halt status
    of its input.

    In every configuration H does correctly decide that its input (P,P)
    never halts. This can be verified beyond all possible doubt by the x86 execution trace of the simulation of P(P) shown below.

    The P(P) of main() only halts because H(P,P) correctly decides that its
    input never halts. This cause-and-effect relationship between the
    simulated P and the executed P proves that the simulated P and the
    executed P are distinctly different computations.

    Because they are different computations the fact that the executed P
    halts does not contradict the fact that the simulated P never halts.

    While H remains in pure simulation mode simulating the input to H(P,P)
    this simulated input never halts thus conclusively proving that H
    decides this input correctly.

    Because H only acts as a pure simulator of its input until after its
    halt status decision has been made it has no behavior that can possibly
    effect the behavior of its input. Because of this H screens out its own
    address range in every execution trace that it examines. This is why we
    never see any instructions of H in any execution trace after an input
    calls H.

    *Halting computation* is any computation that eventually reaches its own
    final state. This criteria divides computations that halt from those
    that merely stop running because their simulation was aborted.

    A Turing machine is said to halt whenever it reaches a configuration
    for which δ is not defined; this is possible because δ is a partial
    function. In fact, we will assume that no transitions are defined for
    any final state, so the Turing machine will halt whenever it enters a
    final state. (Linz:1990:234)

    // 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]

    _main()
    [00000c56](01) 55 push ebp
    [00000c57](02) 8bec mov ebp,esp
    [00000c59](05) 68360c0000 push 00000c36 // push P
    [00000c5e](05) 68360c0000 push 00000c36 // push P
    [00000c63](05) e8fefcffff call 00000966 // call H(P,P)
    [00000c68](03) 83c408 add esp,+08
    [00000c6b](01) 50 push eax
    [00000c6c](05) 6857030000 push 00000357
    [00000c71](05) e810f7ffff call 00000386
    [00000c76](03) 83c408 add esp,+08
    [00000c79](02) 33c0 xor eax,eax
    [00000c7b](01) 5d pop ebp
    [00000c7c](01) c3 ret
    Size in bytes:(0039) [00000c7c]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= =============
    [00000c56][0010172a][00000000] 55 push ebp
    [00000c57][0010172a][00000000] 8bec mov ebp,esp
    [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P
    [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P
    [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36
    [00000c36][002117ca][002117ce] 55 push ebp
    [00000c37][002117ca][002117ce] 8bec mov ebp,esp
    [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
    [00000c3c][002117c6][00000c36] 50 push eax // push P
    [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
    [00000c40][002117c2][00000c36] 51 push ecx // push P
    [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

    We can see that the first seven lines of P repeat. P calls H(P,P) that
    simulates P(P) that calls H(P,P) in a cycle the never stops unless H
    stops simulating its input. When H does stop simulating its input P
    never reaches its final state of [00000c50] therefore never halts even
    though it stops running.

    [00000c36][0025c1f2][0025c1f6] 55 push ebp
    [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
    [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
    [00000c3c][0025c1ee][00000c36] 50 push eax // push P
    [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
    [00000c40][0025c1ea][00000c36] 51 push ecx // push P
    [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped

    [00000c68][0010172a][00000000] 83c408 add esp,+08
    [00000c6b][00101726][00000000] 50 push eax
    [00000c6c][00101722][00000357] 6857030000 push 00000357
    [00000c71][00101722][00000357] e810f7ffff call 00000386
    Input_Halts = 0
    [00000c76][0010172a][00000000] 83c408 add esp,+08
    [00000c79][0010172a][00000000] 33c0 xor eax,eax
    [00000c7b][0010172e][00100000] 5d pop ebp
    [00000c7c][00101732][00000068] c3 ret
    Number_of_User_Instructions(27)
    Number of Instructions Executed(23721)

    *Strachey, C 1965* An impossible program The Computer Journal, Volume
    7, Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313 >>
    *Linz, Peter 1990* An Introduction to Formal Languages and Automata.
    Lexington/Toronto: D. C. Heath and Company.

    --
    Copyright 2021 Pete Olcott

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


    --
    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)
  • From olcott@21:1/5 to wij on Sat Aug 14 12:22:02 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/14/2021 11:35 AM, wij wrote:
    On Sunday, 15 August 2021 at 00:16:20 UTC+8, olcott wrote:
    On 8/14/2021 11:05 AM, wij wrote:
    On Saturday, 14 August 2021 at 23:18:03 UTC+8, olcott wrote:
    This exact same analysis always applies to the input to H(P,P) no matter >>>> how it is called including this example:

    int main()
    {
    P((u32)P);
    }

    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    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

    Because the halting problem only requires that the (at least partial)
    halt decider decide its input correctly the fact that the direct
    invocation of P(P) is not an input to H, means that it is not relevant >>>> to the halting problem.

    I do not know English well, but I (almost every programmer) am sure the halting
    problem means a program H decides whether P(input) will halt or not.
    If the quoted texts is read to you differently, it is the problem of that texts.
    Submit message to the authors.

    The quoted texts are accurate. The (at least partial) halt decider must
    only correctly decide the halt status of its input. Computations that
    are not inputs to the halt decider do not pertain to the halting problem.

    Obviously the quoted text means differently to you and almost all programmers in
    the world. You are addressing your own interpretation. This is OK, but the interpretation is meaningless.

    "the description of a Turing machine M" does not mean Turing machine M.
    If people interpret this to mean Turing machine M they are wrong.

    If the direct invocation of P(P) is not relevant to the halting problem, then
    H can do whatever you like, therefore, meaningless if not garbage.

    The halting problem is only concerned with an at least partial halt
    decider correctly deciding whether or not its input halts, thus it can
    do whatever its wants as long as it does decide the correct halt status
    of its input.


    int H2(Prog P) {
    return 0;
    }
    What is the difference of your H with H2?
    H2 can also correctly (at least partial) answer the halting problem, and can be verified.


    My H has intelligence and can be verified to derive a halt status that corresponds to every halting computation and can be verified to derive a
    halt status that corresponds to that halt status of every input that it determines never halts.

    H is always correct for all:
    (a) halting computations.
    (b) computations that it decides never halt.

    In every configuration H does correctly decide that its input (P,P)
    never halts. This can be verified beyond all possible doubt by the x86
    execution trace of the simulation of P(P) shown below.
    The P(P) of main() only halts because H(P,P) correctly decides that its >>>> input never halts. This cause-and-effect relationship between the
    simulated P and the executed P proves that the simulated P and the
    executed P are distinctly different computations.

    Because they are different computations the fact that the executed P
    halts does not contradict the fact that the simulated P never halts.

    While H remains in pure simulation mode simulating the input to H(P,P) >>>> this simulated input never halts thus conclusively proving that H
    decides this input correctly.

    Because H only acts as a pure simulator of its input until after its
    halt status decision has been made it has no behavior that can possibly >>>> effect the behavior of its input. Because of this H screens out its own >>>> address range in every execution trace that it examines. This is why we >>>> never see any instructions of H in any execution trace after an input
    calls H.

    *Halting computation* is any computation that eventually reaches its own >>>> final state. This criteria divides computations that halt from those
    that merely stop running because their simulation was aborted.

    A Turing machine is said to halt whenever it reaches a configuration
    for which δ is not defined; this is possible because δ is a partial
    function. In fact, we will assume that no transitions are defined for
    any final state, so the Turing machine will halt whenever it enters a
    final state. (Linz:1990:234)

    // 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]

    _main()
    [00000c56](01) 55 push ebp
    [00000c57](02) 8bec mov ebp,esp
    [00000c59](05) 68360c0000 push 00000c36 // push P
    [00000c5e](05) 68360c0000 push 00000c36 // push P
    [00000c63](05) e8fefcffff call 00000966 // call H(P,P)
    [00000c68](03) 83c408 add esp,+08
    [00000c6b](01) 50 push eax
    [00000c6c](05) 6857030000 push 00000357
    [00000c71](05) e810f7ffff call 00000386
    [00000c76](03) 83c408 add esp,+08
    [00000c79](02) 33c0 xor eax,eax
    [00000c7b](01) 5d pop ebp
    [00000c7c](01) c3 ret
    Size in bytes:(0039) [00000c7c]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= =============
    [00000c56][0010172a][00000000] 55 push ebp
    [00000c57][0010172a][00000000] 8bec mov ebp,esp
    [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P
    [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P
    [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P) >>>>
    Begin Local Halt Decider Simulation at Machine Address:c36
    [00000c36][002117ca][002117ce] 55 push ebp
    [00000c37][002117ca][002117ce] 8bec mov ebp,esp
    [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
    [00000c3c][002117c6][00000c36] 50 push eax // push P
    [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
    [00000c40][002117c2][00000c36] 51 push ecx // push P
    [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P) >>>>
    We can see that the first seven lines of P repeat. P calls H(P,P) that >>>> simulates P(P) that calls H(P,P) in a cycle the never stops unless H
    stops simulating its input. When H does stop simulating its input P
    never reaches its final state of [00000c50] therefore never halts even >>>> though it stops running.

    [00000c36][0025c1f2][0025c1f6] 55 push ebp
    [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
    [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
    [00000c3c][0025c1ee][00000c36] 50 push eax // push P
    [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
    [00000c40][0025c1ea][00000c36] 51 push ecx // push P
    [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P) >>>> Local Halt Decider: Infinite Recursion Detected Simulation Stopped

    [00000c68][0010172a][00000000] 83c408 add esp,+08
    [00000c6b][00101726][00000000] 50 push eax
    [00000c6c][00101722][00000357] 6857030000 push 00000357
    [00000c71][00101722][00000357] e810f7ffff call 00000386
    Input_Halts = 0
    [00000c76][0010172a][00000000] 83c408 add esp,+08
    [00000c79][0010172a][00000000] 33c0 xor eax,eax
    [00000c7b][0010172e][00100000] 5d pop ebp
    [00000c7c][00101732][00000068] c3 ret
    Number_of_User_Instructions(27)
    Number of Instructions Executed(23721)

    *Strachey, C 1965* An impossible program The Computer Journal, Volume
    7, Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313 >>>>
    *Linz, Peter 1990* An Introduction to Formal Languages and Automata.
    Lexington/Toronto: D. C. Heath and Company.

    --
    Copyright 2021 Pete Olcott

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


    --
    Copyright 2021 Pete Olcott

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


    --
    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)
  • From olcott@21:1/5 to Richard Damon on Sat Aug 14 13:44:07 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/14/2021 1:32 PM, Richard Damon wrote:
    On 8/14/21 1:22 PM, olcott wrote:
    On 8/14/2021 11:35 AM, wij wrote:
    On Sunday, 15 August 2021 at 00:16:20 UTC+8, olcott wrote:
    On 8/14/2021 11:05 AM, wij wrote:
    On Saturday, 14 August 2021 at 23:18:03 UTC+8, olcott wrote:
    This exact same analysis always applies to the input to H(P,P) no
    matter
    how it is called including this example:

    int main()
    {
    P((u32)P);
    }

    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    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

    Because the halting problem only requires that the (at least partial) >>>>>> halt decider decide its input correctly the fact that the direct
    invocation of P(P) is not an input to H, means that it is not relevant >>>>>> to the halting problem.

    I do not know English well, but I (almost every programmer) am sure
    the halting
    problem means a program H decides whether P(input) will halt or not. >>>>> If the quoted texts is read to you differently, it is the problem of >>>>> that texts.
    Submit message to the authors.

    The quoted texts are accurate. The (at least partial) halt decider must >>>> only correctly decide the halt status of its input. Computations that
    are not inputs to the halt decider do not pertain to the halting
    problem.

    Obviously the quoted text means differently to you and almost all
    programmers in
    the world. You are addressing your own interpretation. This is OK, but
    the
    interpretation is meaningless.

    "the description of a Turing machine M" does not mean Turing machine M.
    If people interpret this to mean Turing machine M they are wrong.

    The INPUT is the description of Turing Machine M.

    The answer is about the behavior of Turing Machine M, which, as pointed
    out, is NOT the input.


    The answer is about the behavior of Turing Machine M corresponding to
    the input. The answer is not about some other Turing machine M that is
    in some other different point in the execution trace.

    Another way to say this is that answer is about the behavior of the pure simulation of the input on its input.

    It is easily verified that

    While H remains in pure simulation mode simulating the input to H(P,P)
    this simulated input never stops running halts thus conclusively proving
    that H decides this input correctly.


    --
    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)
  • From olcott@21:1/5 to dklei...@gmail.com on Sat Aug 14 15:05:18 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/14/2021 2:49 PM, dklei...@gmail.com wrote:
    On Saturday, August 14, 2021 at 9:06:27 AM UTC-7, olcott wrote:
    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    That is not a proper statement of what is at stake. The theorem
    is that there does not exist a Turing Machine which, given the
    description of another Turing Machine, can determine whether
    or not the second Turing Machine halts. The proof is that if such
    a first Turing Machine were to exist we can construction a
    second machine for which the first machine determines halting
    incorrectly.


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


    All that I have to do to refute all of the conventional halting problem
    proofs is to show how H correctly decides that its input H(P,P) never
    halts.

    I have done that, yet people deliberately make sure that to never
    examine the actual analysis of the halt status decision of the actual
    input to H. Instead they always dishonestly change the subject to
    another computation that is not the input to H.

    --
    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)
  • From olcott@21:1/5 to Richard Damon on Sat Aug 14 15:52:11 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/14/2021 3:39 PM, Richard Damon wrote:
    On 8/14/21 2:33 PM, olcott wrote:
    On 8/14/2021 12:10 PM, Richard Damon wrote:
    On 8/14/21 12:16 PM, olcott wrote:
    On 8/14/2021 11:05 AM, wij wrote:
    On Saturday, 14 August 2021 at 23:18:03 UTC+8, olcott wrote:
    This exact same analysis always applies to the input to H(P,P) no
    matter
    how it is called including this example:

    int main()
    {
    P((u32)P);
    }

    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    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

    Because the halting problem only requires that the (at least partial) >>>>>> halt decider decide its input correctly the fact that the direct
    invocation of P(P) is not an input to H, means that it is not relevant >>>>>> to the halting problem.
       I do not know English well, but I (almost every programmer) am sure >>>>> the halting
    problem means a program H decides whether P(input) will halt or not. >>>>> If the quoted texts is read to you differently, it is the problem of >>>>> that texts.
    Submit message to the authors.


    The quoted texts are accurate. The (at least partial) halt decider must >>>> only correctly decide the halt status of its input. Computations that
    are not inputs to the halt decider do not pertain to the halting
    problem.


    This is the point where you use of English is incorrect, and you need to >>> restudy English so you understand what you are saying.

    *Inputs* are NEVER *Computations* in and of themselves, but are merely
    the string representations of the ACTUAL Computations.

    As such, 'inputs' don't halt or be non-halting, only the machines they
    represent.
    The input "description of an arbitrary computer program" is the basis
    for the halt status decision.



    The input is what the program uses to make its decision, the right
    answer is what the actual machine does.


    Because the input to H(P,P) is at a different point int the execution
    trace than the P of int main(){ P(P); } it is a different computation
    having different behavior than the input to H(P,P).

    If we are not damn liars and know the x86 language sufficiently well
    enough then we can see that the simulation of the input to H precisely
    matches the x86 source-code of P on input P therefore the pure
    simulation of P on input P is perfectly correct.

    Damn liars that know the x86 language well enough can see this too.

    _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(P,P)
    [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]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

    [00000c36][0025c1f2][0025c1f6] 55 push ebp [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50 push eax // push P [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51 push ecx // push P [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped


    You don't seem to understand the difference.

    The program uses unsound logic in its analysis and thus gets a wrong
    answer. (It assumes that H will NEVER abort, when it just is a won't
    abort until type of program). Until is not Never, so it get the answer
    wrong.



    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Sat Aug 14 16:06:36 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/14/2021 3:43 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    The P(P) of main() only halts because...

    As you say, P(P) halts.

    *Halting computation* is any computation that eventually reaches its
    own final state. This criteria divides computations that halt from
    those that merely stop running because their simulation was aborted.

    No. There is no "special kind of halting". The computation M(I) either halts or it does not. H(M, I) should be false if, and only if, M(I)
    does not halt.

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

    P(P) halts, yet H(P, P) is false. That's the wrong answer.


    Because the input to H(P,P) is at a different point in the execution
    trace than the P of int main(){ P(P); } it is a different computation
    having different behavior than the input to H(P,P).

    Why are you still hiding H? Is it because you have still not figured
    out how to nest a call to the simulator you are using?

    That part alone took me three months after all the rest of the x86utm
    operating system was complete.

    If people can't begin to understand that seven lines of x86 code of P
    are stuck in infinitely nested simulation while H remains in pure
    simulator mode after many months of discussion then adding the much more complexity of the details of how simulation works is not going to help
    their understanding.

    All they really need to know is that infinitely nested simulation has computationally equivalent halting behavior to infinite recursion.

    Also I want to keep this in reserve as totally unpublished work so that
    a publisher will have some key material that has never been previously disclosed.

    Fortunately "we"
    (i.e. everyone but you) can see that H is wrong without even seeing the
    code. Who is included in the "we" of the subject line? Have you found someone else who thinks that false is the correct return from a partial
    halt decider called with arguments that represent a halting computation?


    _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]

    [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

    [00000c36][0025c1f2][0025c1f6] 55 push ebp [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50 push eax // push P [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51 push ecx // push P [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped

    If you can "see" how P is able to break out of its infinitely nested
    simulation while H remains in pure simulator mode please feel free to
    share.

    --
    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)
  • From olcott@21:1/5 to Malcolm McLean on Sun Aug 15 08:36:00 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/15/2021 4:39 AM, Malcolm McLean wrote:
    On Sunday, 15 August 2021 at 05:39:10 UTC+1, olcott wrote:
    On 8/14/2021 5:56 PM, Ben Bacarisse wrote:
    Jeff Barnett <j...@notatt.com> writes:

    On 8/14/2021 2:43 PM, Ben Bacarisse wrote:
    olcott <No...@NoWhere.com> writes:

    The P(P) of main() only halts because...
    As you say, P(P) halts.

    *Halting computation* is any computation that eventually reaches its >>>>>> own final state. This criteria divides computations that halt from >>>>>> those that merely stop running because their simulation was aborted. >>>>> No. There is no "special kind of halting". The computation M(I) either >>>>> halts or it does not. H(M, I) should be false if, and only if, M(I)
    does not halt.

    void P(u32 x)
    {
    if (H(x, x))
    HERE: goto HERE;
    }
    P(P) halts, yet H(P, P) is false. That's the wrong answer.
    Why are you still hiding H? Is it because you have still not figured >>>>> out how to nest a call to the simulator you are using? Fortunately "we" >>>>> (i.e. everyone but you) can see that H is wrong without even seeing the >>>>> code. Who is included in the "we" of the subject line? Have you found >>>>> someone else who thinks that false is the correct return from a partial >>>>> halt decider called with arguments that represent a halting computation? >>>>
    I have questions about the PO simulator I hope someone can answer. It
    perhaps concerns memory mapping: First - is every instance of a use at >>>> different levels in its own address space? Second - if not, is there
    any way to know when an address is reported, which simulator instance
    is being reported on? When the dumb bunny (PO expression) notes that
    the same address is reached a second time without a conditional branch >>>> being executed, is there any assurance that the addresses are noted
    from the same instance of the simulation? And finally, how can one
    determine if it's the same address twice without doing some sort of
    compare and branch? Thanks in advance for any sort of enlightenment.

    You won't get a straight answer from PO, but I don't think there is any
    nested simulation happening at all. PO "knows" it's that same a
    recursion, so he just has recursive calls traced from "outside". I may
    No this is not possible. There is no possible way to use ordinary
    recursion to implement nested x86 emulation without memory corruption of
    the stack. I explained all of the technical details of context
    switching: Here is a link that does a better job:

    https://en.wikipedia.org/wiki/Context_switch

    Each virtual machine has its own registers, stack and RAM. Once the
    virtual machine environment is set up, allocating the stack and RAM and
    other house keeping functions a context switch only requires saving and
    restoring all the machine registers.

    We can write a ZX81 emulator on a modern machine. A ZX81 has 4K ROM
    and 1K RAM. So our first line can be a "virualmem = malloc(1024 * 5). We then set up everything else in that memory space.
    However the ZX81 emulator cannot emulate another ZX81, since it has only
    1K RAM to play with, and the virtual machine needs 5K.
    You'll get this problem whenever you try to allow nested emulation on a random-access memory model machine.

    Turing machines don't have this problem. Write a UTM, and a "Hello world" program, and
    UTM<Hello> with output "Hello world" on the tape.
    UTM<UTM><Hello> will also output "Hello world" on the tape. You can stack up as many UTMs as you like without any reprogramming. It might get very slow, but it will eventually finish.

    What you can do is treat memory allocation as a special function. Then you can nest simulations.


    Yes I do that.
    It does not require knowing any of those details to see how totally
    blatantly obvious it is that:

    While H remains in pure simulation mode simulating the input to H(P,P)
    this simulated input never stops running thus conclusively proving that
    when H decides this input never halts it is correct.

    _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]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

    [00000c36][0025c1f2][0025c1f6] 55 push ebp [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50 push eax // push P [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51 push ecx // push P [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped



    --
    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)
  • From olcott@21:1/5 to wij on Sun Aug 15 11:44:35 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/15/2021 9:45 AM, wij wrote:
    On Sunday, 15 August 2021 at 21:45:09 UTC+8, olcott wrote:
    On 8/15/2021 2:50 AM, wij wrote:
    On Sunday, 15 August 2021 at 02:24:42 UTC+8, olcott wrote:
    On 8/14/2021 1:09 PM, wij wrote:
    On Sunday, 15 August 2021 at 01:22:11 UTC+8, olcott wrote:
    On 8/14/2021 11:35 AM, wij wrote:
    On Sunday, 15 August 2021 at 00:16:20 UTC+8, olcott wrote:
    On 8/14/2021 11:05 AM, wij wrote:
    On Saturday, 14 August 2021 at 23:18:03 UTC+8, olcott wrote: >>>>>>>>>> This exact same analysis always applies to the input to H(P,P) no matter
    how it is called including this example:

    int main()
    {
    P((u32)P);
    }

    the Turing machine halting problem. Simply stated, the problem >>>>>>>>>> is: given the description of a Turing machine M and an input w, >>>>>>>>>> does M, when started in the initial configuration q0w, perform a >>>>>>>>>> computation that eventually halts? (Linz:1990:317).

    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 >>>>>>>>>>
    Because the halting problem only requires that the (at least partial)
    halt decider decide its input correctly the fact that the direct >>>>>>>>>> invocation of P(P) is not an input to H, means that it is not relevant
    to the halting problem.

    I do not know English well, but I (almost every programmer) am sure the halting
    problem means a program H decides whether P(input) will halt or not. >>>>>>>>> If the quoted texts is read to you differently, it is the problem of that texts.
    Submit message to the authors.

    The quoted texts are accurate. The (at least partial) halt decider must
    only correctly decide the halt status of its input. Computations that >>>>>>>> are not inputs to the halt decider do not pertain to the halting problem.

    Obviously the quoted text means differently to you and almost all programmers in
    the world. You are addressing your own interpretation. This is OK, but the
    interpretation is meaningless.
    "the description of a Turing machine M" does not mean Turing machine M. >>>>>> If people interpret this to mean Turing machine M they are wrong.

    Then, both Linz and the author of https://en.wikipedia.org/wiki/Halting_problem
    are also wrong, I and almost all programmers in the world can guarantee you this.

    If both authors are also wrong, replying the rest message is meaningless. >>>>> You need to submit your interpretation to Linz and the author of the wiki.

    I think that the problem is that your English is not so good.
    The Linz text and the Wiki text are correct.
    Linz retired many years ago.

    In your recent post somewhere, you said:
    "I made my refutation of Linz a little more clear by changing all of the >>> subscripts to be numeric. My refutation of Linz cannot be properly
    understood until after my refutation of simplified Linz / Strachey is
    first understood..."
    Now, you changed mind to say "The Linz text and the Wiki text are correct." >>>
    This text right here is correct:
    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    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
    All of the rest of the text that "proves" the halting problem cannot be
    solved it incorrect.

    Which one did you mean:
    1. All of the rest of the text that "proves" the halting problem cannot be solved incorrect. (still ambiguous)
    2. All of the rest of the text that "proves" the halting problem cannot
    solve incorrect. (ambiguous)
    3. All of the rest of the text that "proves" the halting problem cannot be solved, it is incorrect.


    All of the rest of the text that "proves" the halting problem cannot be
    solved <IS> incorrect.

    There are much more inconsistent statements in your posts, like "H is a total
    function",...,etc. (I do not have time to re-find them).

    H is a pure function of its inputs in that all of the nested simulations
    are simply data derived entirely on the basis of this inputs.

    From your description:
    "The x86utm operating system uses a single contiguous block of RAM to
    most precisely map to the concept of a single contiguous Turing machine
    tape. All of the code and data of the virtual machines that it executes
    are contained in this single contiguous block. There is no virtual
    memory paging in the x86utm operating system."

    I believe your H is a 'pure function', you are actually dealing with two "C" function calls. H is not really a simulator as you keeps calling it so.
    Show me how H(P,P) takes its input P as 'simple data'.


    The x86utm operating system is build from an x86 emulator capable of
    emulating all of the 80386 instructions using 4 GB of RAM.

    The following x86utm operating system function calls the x86 emulator to emulate exactly one instruction of the slave process and then return to
    the calling process. It also decodes the slave instruction that was
    emulated so that it can be stored in the execution trace.

    u32 DebugStep(Registers* master_state,
    Registers* slave_state,
    Decoded_Line_Of_Code* decoded) {}

    I hate to say that your programming level is very low because this has noting to do with the HP proof. I think many others know x86 and C languages and programming skills better than you do. No need to repeat posting the compiled assembly code fragment and pretend you know better and others cannot see it.


    It is ridiculously foolish to claim that P on input P has nothing to do
    with the halting problem proofs:

    Now we construct a new Turing machine D with H as a subroutine.
    This new TM calls H to determine what M does when the input to
    M is its own description ⟨M⟩. Once D has determined this information,
    it does the opposite. (Sipser:1997:165)

    It remains ridiculously foolish for people claiming to fully understand
    the x86 language to disagree with the following statement:

    While H remains in pure simulation mode simulating the input to H(P,P)
    this simulated input never stops running thus conclusively proving that
    when H decides this input never halts it is correct.

    // 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]

    _main()
    [00000c56](01) 55 push ebp
    [00000c57](02) 8bec mov ebp,esp
    [00000c59](05) 68360c0000 push 00000c36 // push P
    [00000c5e](05) 68360c0000 push 00000c36 // push P
    [00000c63](05) e8fefcffff call 00000966 // call H(P,P)
    [00000c68](03) 83c408 add esp,+08
    [00000c6b](01) 50 push eax
    [00000c6c](05) 6857030000 push 00000357
    [00000c71](05) e810f7ffff call 00000386
    [00000c76](03) 83c408 add esp,+08
    [00000c79](02) 33c0 xor eax,eax
    [00000c7b](01) 5d pop ebp
    [00000c7c](01) c3 ret
    Size in bytes:(0039) [00000c7c]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= [00000c56][0010172a][00000000] 55 push ebp [00000c57][0010172a][00000000] 8bec mov ebp,esp [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

    [00000c36][0025c1f2][0025c1f6] 55 push ebp [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50 push eax // push P [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51 push ecx // push P [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped


    What does your bible say about a liar? Does it matter? Surely, it does matter
    if it applies to others, not you (you can restate it in your flavor).
    Then, what else evil you cannot do, none.

    子曰:人而無信不知其可
    Confucius says: If a man does not keep his word, what is he good for?

    If the direct invocation of P(P) is not relevant to the halting problem, then
    H can do whatever you like, therefore, meaningless if not garbage. >>>>>>>>>
    The halting problem is only concerned with an at least partial halt >>>>>>>> decider correctly deciding whether or not its input halts, thus it can >>>>>>>> do whatever its wants as long as it does decide the correct halt status
    of its input.


    int H2(Prog P) {
    return 0;
    }
    What is the difference of your H with H2?
    H2 can also correctly (at least partial) answer the halting problem, and can
    be verified.

    My H has intelligence and can be verified to derive a halt status that >>>>>> corresponds to every halting computation and can be verified to derive a >>>>>> halt status that corresponds to that halt status of every input that it >>>>>> determines never halts.

    H is always correct for all:
    (a) halting computations.
    (b) computations that it decides never halt.
    In every configuration H does correctly decide that its input (P,P) >>>>>>>> never halts. This can be verified beyond all possible doubt by the x86 >>>>>>>> execution trace of the simulation of P(P) shown below.
    The P(P) of main() only halts because H(P,P) correctly decides that its
    input never halts. This cause-and-effect relationship between the >>>>>>>>>> simulated P and the executed P proves that the simulated P and the >>>>>>>>>> executed P are distinctly different computations.

    Because they are different computations the fact that the executed P >>>>>>>>>> halts does not contradict the fact that the simulated P never halts. >>>>>>>>>>
    While H remains in pure simulation mode simulating the input to H(P,P)
    this simulated input never halts thus conclusively proving that H >>>>>>>>>> decides this input correctly.

    Because H only acts as a pure simulator of its input until after its >>>>>>>>>> halt status decision has been made it has no behavior that can possibly
    effect the behavior of its input. Because of this H screens out its own
    address range in every execution trace that it examines. This is why we
    never see any instructions of H in any execution trace after an input
    calls H.

    *Halting computation* is any computation that eventually reaches its own
    final state. This criteria divides computations that halt from those >>>>>>>>>> that merely stop running because their simulation was aborted. >>>>>>>>>>
    A Turing machine is said to halt whenever it reaches a configuration >>>>>>>>>> for which δ is not defined; this is possible because δ is a partial
    function. In fact, we will assume that no transitions are defined for
    any final state, so the Turing machine will halt whenever it enters a
    final state. (Linz:1990:234)

    // 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]

    _main()
    [00000c56](01) 55 push ebp
    [00000c57](02) 8bec mov ebp,esp
    [00000c59](05) 68360c0000 push 00000c36 // push P
    [00000c5e](05) 68360c0000 push 00000c36 // push P
    [00000c63](05) e8fefcffff call 00000966 // call H(P,P)
    [00000c68](03) 83c408 add esp,+08
    [00000c6b](01) 50 push eax
    [00000c6c](05) 6857030000 push 00000357
    [00000c71](05) e810f7ffff call 00000386
    [00000c76](03) 83c408 add esp,+08
    [00000c79](02) 33c0 xor eax,eax
    [00000c7b](01) 5d pop ebp
    [00000c7c](01) c3 ret
    Size in bytes:(0039) [00000c7c]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= =============
    [00000c56][0010172a][00000000] 55 push ebp
    [00000c57][0010172a][00000000] 8bec mov ebp,esp
    [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P >>>>>>>>>> [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P >>>>>>>>>> [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36 >>>>>>>>>> [00000c36][002117ca][002117ce] 55 push ebp
    [00000c37][002117ca][002117ce] 8bec mov ebp,esp
    [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08]
    [00000c3c][002117c6][00000c36] 50 push eax // push P
    [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08]
    [00000c40][002117c2][00000c36] 51 push ecx // push P
    [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

    We can see that the first seven lines of P repeat. P calls H(P,P) that
    simulates P(P) that calls H(P,P) in a cycle the never stops unless H >>>>>>>>>> stops simulating its input. When H does stop simulating its input P >>>>>>>>>> never reaches its final state of [00000c50] therefore never halts even
    though it stops running.

    [00000c36][0025c1f2][0025c1f6] 55 push ebp
    [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp
    [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08]
    [00000c3c][0025c1ee][00000c36] 50 push eax // push P
    [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08]
    [00000c40][0025c1ea][00000c36] 51 push ecx // push P
    [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped >>>>>>>>>>
    [00000c68][0010172a][00000000] 83c408 add esp,+08
    [00000c6b][00101726][00000000] 50 push eax
    [00000c6c][00101722][00000357] 6857030000 push 00000357
    [00000c71][00101722][00000357] e810f7ffff call 00000386
    Input_Halts = 0
    [00000c76][0010172a][00000000] 83c408 add esp,+08
    [00000c79][0010172a][00000000] 33c0 xor eax,eax
    [00000c7b][0010172e][00100000] 5d pop ebp
    [00000c7c][00101732][00000068] c3 ret
    Number_of_User_Instructions(27)
    Number of Instructions Executed(23721)

    *Strachey, C 1965* An impossible program The Computer Journal, Volume
    7, Issue 4, January 1965, Page 313, https://doi.org/10.1093/comjnl/7.4.313

    *Linz, Peter 1990* An Introduction to Formal Languages and Automata. >>>>>>>>>> Lexington/Toronto: D. C. Heath and Company.

    --
    Copyright 2021 Pete Olcott

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


    --
    Copyright 2021 Pete Olcott

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


    --
    Copyright 2021 Pete Olcott

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


    --
    Copyright 2021 Pete Olcott

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


    --
    Copyright 2021 Pete Olcott

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


    --
    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)
  • From olcott@21:1/5 to Mike Terry on Sun Aug 15 12:16:55 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/15/2021 9:46 AM, Mike Terry wrote:
    On 14/08/2021 22:20, Jeff Barnett wrote:
    On 8/14/2021 2:43 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    The P(P) of main() only halts because...

    As you say, P(P) halts.

    *Halting computation* is any computation that eventually reaches its
    own final state. This criteria divides computations that halt from
    those that merely stop running because their simulation was aborted.

    No.  There is no "special kind of halting".  The computation M(I) either >>> halts or it does not.  H(M, I) should be false if, and only if, M(I)
    does not halt.

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

    P(P) halts, yet H(P, P) is false.  That's the wrong answer.

    Why are you still hiding H?  Is it because you have still not figured
    out how to nest a call to the simulator you are using?  Fortunately "we" >>> (i.e. everyone but you) can see that H is wrong without even seeing the
    code.  Who is included in the "we" of the subject line?  Have you found >>> someone else who thinks that false is the correct return from a partial
    halt decider called with arguments that represent a halting computation?

    I have questions about the PO simulator I hope someone can answer. It
    perhaps concerns memory mapping:

    First - is every instance of a use at different levels in its own
    address space?

    I've tried to get PO to clarify that, and it always /seems/ that he is suggesting yes [while avoiding any direct answer] but I have no
    confidence whatsoever that he understands what everybody else would understand by "its own address space".


    There is a single contiguous block of RAM that is used by all of the
    virtual machine and the halt decider. Whenever H is called it creates a separate context having its own Registers, RAM and stack space. It
    performs its x86 emulation on its input virtual machine in the separate
    process context. Just like recursion the executable code of every
    instance of P and H are at the same fixed machine address.

    He has definitely said that each simulation has its own stack and
    registers, but my bet would be that they are more like your typical OS threads, running in the same address space.  (We could probably find out
    by quizzing him on sharing of globals etc. and giving him concrete
    examples which he could understand.  But it might take a lot of work,
    and for what at the end?  Or more reasonably, if he published all his
    source code as he maintained he would for around two years, we could
    answer these sorts of questions for ourselves...)


    Until people quit refuting this very obvious truth they consistently
    prove that they are far too disingenuous to deserve any additional
    details that would only give them an excuse to make sure that they
    always go off on tangents and dodge the key relevant points:

    While H remains in pure simulation mode simulating the input to H(P,P)
    this simulated input never stops running thus conclusively proving that
    when H decides this input never halts it is correct.

    // 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]

    _main()
    [00000c56](01) 55 push ebp
    [00000c57](02) 8bec mov ebp,esp
    [00000c59](05) 68360c0000 push 00000c36 // push P
    [00000c5e](05) 68360c0000 push 00000c36 // push P
    [00000c63](05) e8fefcffff call 00000966 // call H(P,P)
    [00000c68](03) 83c408 add esp,+08
    [00000c6b](01) 50 push eax
    [00000c6c](05) 6857030000 push 00000357
    [00000c71](05) e810f7ffff call 00000386
    [00000c76](03) 83c408 add esp,+08
    [00000c79](02) 33c0 xor eax,eax
    [00000c7b](01) 5d pop ebp
    [00000c7c](01) c3 ret
    Size in bytes:(0039) [00000c7c]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= [00000c56][0010172a][00000000] 55 push ebp [00000c57][0010172a][00000000] 8bec mov ebp,esp [00000c59][00101726][00000c36] 68360c0000 push 00000c36 // push P [00000c5e][00101722][00000c36] 68360c0000 push 00000c36 // push P [00000c63][0010171e][00000c68] e8fefcffff call 00000966 // call H(P,P)

    Begin Local Halt Decider Simulation at Machine Address:c36 [00000c36][002117ca][002117ce] 55 push ebp [00000c37][002117ca][002117ce] 8bec mov ebp,esp [00000c39][002117ca][002117ce] 8b4508 mov eax,[ebp+08] [00000c3c][002117c6][00000c36] 50 push eax // push P [00000c3d][002117c6][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][002117c2][00000c36] 51 push ecx // push P [00000c41][002117be][00000c46] e820fdffff call 00000966 // call H(P,P)

    [00000c36][0025c1f2][0025c1f6] 55 push ebp [00000c37][0025c1f2][0025c1f6] 8bec mov ebp,esp [00000c39][0025c1f2][0025c1f6] 8b4508 mov eax,[ebp+08] [00000c3c][0025c1ee][00000c36] 50 push eax // push P [00000c3d][0025c1ee][00000c36] 8b4d08 mov ecx,[ebp+08] [00000c40][0025c1ea][00000c36] 51 push ecx // push P [00000c41][0025c1e6][00000c46] e820fdffff call 00000966 // call H(P,P)
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped


    Second - if not, is there any way to know when an address is reported,
    which simulator instance is being reported on?

    I suggested he needed to provide that last year.  And at one point he
    DID change his trace to show the emulation level, so it's not like
    there's any coding difficulty!  But then it was perfectly clear that he
    was correlating trace entries together from completely separate
    emulation levels, so the illusion that it was a "loop" in the normal
    (single) processor-trace sense was lessened.  He subsequently removed
    the column, claiming as excuse that it confused people.

    I'd say this is PO misunderstanding the difference between
    call-recursion and emulation-recursion.  The former can /only/ be broken
    by code at the deepest recursion level which then percolates up to the
    top level, like when we calculate n factorial recursively. Emulation-recursion /can/ also break out this way, but with emulation
    there is a second possibility - the break can be from the /top/ level
    which simply decides not to emulate any more.  The fact that the deepest inner emulations appear to be repeating doesn't mean that they will go
    on forever, because an outer level can always just give up emulating and
    get on with whatever is next.


    If I did not understand this then I would have not explained it this
    same way many dozens of times.

    I suppose without an emulation-id column we can probably work stuff out
    based on the overall flow of the trace together with knowledge about the program and what H is doing and so on.  (But why should this be required when it's an essential part of the meaning of a trace entry?)

    When the dumb bunny (PO expression) notes that the same address is
    reached a second time without a conditional branch being executed, is
    there any assurance that the addresses are noted from the same
    instance of the simulation?

    I can give you an assurance of exactly the opposite - they are
    definitely from /different/ emulation levels!  (I think you know that, right?) PO tries to present them to look as much as possible like a
    pattern of behaviour for a /single/ processor, because then he would
    have "call recursion" which can only break inner-to-outer, and his
    "processor trace" could provide some level of evidence that that won't happen. (Also I'm remebering his recent remarks about the processor "[..having no way to escape from the recursion..]" which might be
    explained as PO not understanding the call/recursion distinction...)


    I want to eliminate the extra 396 pages of extraneous detail because
    people here are finding it next to impossible to understand 7 lines of
    x86 code when this code has been repeatedly explained to them hundreds
    of times over many months. Providing an extra 396 pages of detail
    certainly cannot possibly help in this case.

    In the past PO has said his rule applies equally for call-recursion and emulation-recursion, no difference, while repeating something about "equivalent computation", but he has no real /understanding/ of that
    phrase and certainly no /proof/ of soundness even for the simple call-recursion case, so it's just the usual unsupported claims.  (And
    there is no prospect of ever going further than this - PO is simply not capable of "proving" anything and I doubt he understands what that even means.)

    The emulation recursion and the call recursion have computationally
    equivalent halting behavior as proven by the following execution trace
    compared to the above execution trace of the simulation of P on P.

    void Infinite_Recursion()
    {
    Infinite_Recursion();
    }

    int main()
    {
    Output("Input_Halts = ", H0((u32)Infinite_Recursion));
    }

    _Infinite_Recursion()
    [00000dc2](01) 55 push ebp
    [00000dc3](02) 8bec mov ebp,esp
    [00000dc5](05) e8f8ffffff call 00000dc2
    [00000dca](01) 5d pop ebp
    [00000dcb](01) c3 ret
    Size in bytes:(0010) [00000dcb]

    _main()
    [00000e72](01) 55 push ebp
    [00000e73](02) 8bec mov ebp,esp
    [00000e75](05) 68c20d0000 push 00000dc2
    [00000e7a](05) e873fdffff call 00000bf2
    [00000e7f](03) 83c404 add esp,+04
    [00000e82](01) 50 push eax
    [00000e83](05) 6823030000 push 00000323
    [00000e88](05) e8c5f4ffff call 00000352
    [00000e8d](03) 83c408 add esp,+08
    [00000e90](02) 33c0 xor eax,eax
    [00000e92](01) 5d pop ebp
    [00000e93](01) c3 ret
    Size in bytes:(0034) [00000e93]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= ...[00000e72][00101a85][00000000] 55 push ebp ...[00000e73][00101a85][00000000] 8bec mov ebp,esp ...[00000e75][00101a81][00000dc2] 68c20d0000 push 00000dc2 ...[00000e7a][00101a7d][00000e7f] e873fdffff call 00000bf2

    Begin Local Halt Decider Simulation at Machine Address:dc2 ...[00000dc2][00211b29][00211b2d] 55 push ebp ...[00000dc3][00211b29][00211b2d] 8bec mov ebp,esp ...[00000dc5][00211b25][00000dca] e8f8ffffff call 00000dc2 ...[00000dc2][00211b21][00211b29] 55 push ebp ...[00000dc3][00211b21][00211b29] 8bec mov ebp,esp ...[00000dc5][00211b1d][00000dca] e8f8ffffff call 00000dc2
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped

    ...[00000e7f][00101a85][00000000] 83c404 add esp,+04 ...[00000e82][00101a81][00000000] 50 push eax ...[00000e83][00101a7d][00000323] 6823030000 push 00000323 ---[00000e88][00101a7d][00000323] e8c5f4ffff call 00000352
    Input_Halts = 0
    ...[00000e8d][00101a85][00000000] 83c408 add esp,+08 ...[00000e90][00101a85][00000000] 33c0 xor eax,eax ...[00000e92][00101a89][00100000] 5d pop ebp ...[00000e93][00101a8d][00000044] c3 ret Number_of_User_Instructions(18)
    Number of Instructions Executed(823)

    And finally, how can one determine if it's the same address twice
    without doing some sort of compare and branch?

    OK, for PO's H, there are obviously hidden conditional branch
    instructions within H, which is why PO has to come up with some wording
    to convince himself that H can be totally ignored for whatever reason.

    Because H only acts as a pure simulator of its input until after its
    halt status decision has been made it has no behavior that can possibly
    effect the behavior of its input. Because of this H screens out its own
    address range in every execution trace that it examines. This is why we
    never see any instructions of H in any execution trace after an input
    calls H.

    But drilling down on this seems overkill when PO hasn't even presented
    any plausible argument (let alone proof!) that the detection rule being
    used is sound.

    It is the same rule used in the Infinite_Recursion() shown above.

    What would we be trying to disprove and why? :)  PO has
    agreed that H^(H^) halts, and that H(H^,H^) returns not-halting, so
    that's it.


    int main(){ P(P); } and int main(){ Simulate(P,P); } are computationally equivalent and have the same halting behavior.

    Because the P of H(P,P) is at a different point in the execution trace
    than the above two cases it is not computationally equivalent to the
    above two cases. Because it is not computationally equivalent it can
    have different halting behavior.

    At least in the end it must be PO's responsibility to present /proofs/
    of anything he claims, but now we've gone like 100 miles beyond his capabilities - a complete non-starter...

    Mike.


    When people point out any of my "mistakes" (besides typos) they are only pointing out their own lack of understanding.

    --
    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)
  • From olcott@21:1/5 to Mike Terry on Sun Aug 15 12:25:01 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/15/2021 10:17 AM, Mike Terry wrote:
    On 15/08/2021 00:27, Richard Damon wrote:
    On 8/14/21 6:56 PM, Ben Bacarisse wrote:
    Jeff Barnett <jbb@notatt.com> writes:

    On 8/14/2021 2:43 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    The P(P) of main() only halts because...
    As you say, P(P) halts.

    *Halting computation* is any computation that eventually reaches its >>>>>> own final state. This criteria divides computations that halt from >>>>>> those that merely stop running because their simulation was aborted. >>>>> No. There is no "special kind of halting". The computation M(I)
    either
    halts or it does not. H(M, I) should be false if, and only if, M(I) >>>>> does not halt.

    void P(u32 x)
    {
    if (H(x, x))
    HERE: goto HERE;
    }
    P(P) halts, yet H(P, P) is false. That's the wrong answer.
    Why are you still hiding H? Is it because you have still not figured >>>>> out how to nest a call to the simulator you are using? Fortunately
    "we"
    (i.e. everyone but you) can see that H is wrong without even seeing
    the
    code. Who is included in the "we" of the subject line? Have you
    found
    someone else who thinks that false is the correct return from a
    partial
    halt decider called with arguments that represent a halting
    computation?

    I have questions about the PO simulator I hope someone can answer. It
    perhaps concerns memory mapping: First - is every instance of a use at >>>> different levels in its own address space? Second - if not, is there
    any way to know when an address is reported, which simulator instance
    is being reported on? When the dumb bunny (PO expression) notes that
    the same address is reached a second time without a conditional branch >>>> being executed, is there any assurance that the addresses are noted
    from the same instance of the simulation? And finally, how can one
    determine if it's the same address twice without doing some sort of
    compare and branch? Thanks in advance for any sort of enlightenment.

    You won't get a straight answer from PO, but I don't think there is any
    nested simulation happening at all. PO "knows" it's that same a
    recursion, so he just has recursive calls traced from "outside". I may
    be wrong, of course, but this is one reason I think H is being kept
    hidden -- it does not do what says.


    He actually has leaked a fair amount about how the system works. H isn't
    actually a simulator, but an 'API Entry' into the x86utm system that has
    the real simulator, and calls into H as supposed to setup a new 'nested'
    level of simulation.

    My impression is that H is part of the application code rather than an
    OS call, but within H there are calls to PO's simulation primitives
    which are trapped by x86utm.exe and implemented within x86utm. H would
    still have the task of inspecting the (nested) emulation trace entries
    to detect what it decides to be non-halting behaviour. (But then PO has talked about a "global decider" which is part of the OS, so maybe my impression is completely wrong! To be relevent to Linz, the deciding
    logic at least must be in the application rather than in x86utm.)


    Now that I created

    int Simulate(u32 P, u32 I)
    {
    ((int(*)(int))P)(I);
    return 1;
    }

    The global halt decider is fully obsolete.

    I am (of course) aware that the above function directly executes rather
    that emulates its input, none-the-less it provides a very simple way
    that is very easy to understand to provide the computational equivalent
    of simulation.


    It sounds like these nested simulations are given their own stacks and
    'user' code isn't supposed to be able to store data anywhere but on the
    stack, so that is supposed to be enough for a new environment, since he
    erroneously puts everything inside one code segment. (This means that H
    isn't a 'Universal' Halt Decider, as its input isn't an arbitrary
    machine.

    This would be one reason you can't 'copy' H, is that H isn't really the
    code but just an API (and if he allowed copying, his nesting detection
    breaks).

    One side effect of this is that I am not sure if his system can actually
    really handle finitely but multi-level simulations as at least some of
    the leaked implementations made H not really a computation as it used
    static memory to communicate between H and the OS.


    I also wonder if a computation built on P1 using H to decide on P2 which
    used H to decide on P3 could return the answer from P3 to P2.

    This structure could be used to solve the twins prime conjecture if the
    Halt decider actually worked. P1 would ask P2 to find the highest twin
    prime. If it is non-halting there is no highest twin prime.

    P2 would iterate through the twin primes starting at say 3,5 and ask P3
    to find the next one. If it find one, then it updates to that point and
    uses it again to find the next highest. If P2 is at the highest, then P3
    would be non-halting, and P2 would get the non-halting answer and could
    tell P1 what is the highest twin prime.

    P3 just takes its input and searches to find the next highest twin prime
    from there. If there isn't one it will just be non-halting.

    The problem is that just because P3 becomes non-halting isn't grounds to
    call P1 or P2 non-halting, as P3 becoming non-halting is the halting
    condition of P2. It is only if for every problem that P2 gives P3 that
    it always finds an answer that P2 becomes non-halting, and P1 then knows
    that the answer to the question is that there is no highest twin prime.
    (P1 halts in all cases).

    The slight problem is that his current definition of H doesn't seem to
    allow the caller of H to get the 'answer' from the machine it is
    running, so you have to do everything twice, first determine that it
    WOULD halt, then just call it to get the answer.


    Maybe, but the emulating user code has access to the trace of the
    emulated program, so in principle it should be able to work out what
    that program returned. E.g. it can track that it finished by loading RAX
    with (say) 1 then returned (terminated), meaning that it returned 1.

    Mike.


    The executed (rather than simulated) instance of H has every relevant
    detail of all of its nested emulations as its own data that is derived
    as a pure function of its 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)
  • From olcott@21:1/5 to Ben Bacarisse on Mon Aug 16 17:49:32 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/15/2021 8:07 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/15/2021 3:31 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

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

    If H(P, P) does not give the halting status of P(P) it is useless.

    In other words your knowledge of infinite recursive invocation is on
    par with your knowledge of operating system context switching?

    P(P) halts.

    Imagine if you'd been honest about this two and half years ago? "I have >>> a function H such that H(H_Hat, H_Hat) == 0 so H_Hat(H_Hat) halts." No
    one would care.

    I finally have this one untangled:
    int main() { P(P); } is computationally equivalent to
    int main() { Simulate(P,P); }

    Because they are computationally equivalent they have the same halting
    behavior, however:

    Neither of them is computationally equivalent to the H(P,P) called
    from P because the different placement in the execution trace changes
    the halting behavior of P(P).

    H(M, I) is supposed to report the halting or otherwise of M(I). You
    don't claim that your H can do this in all cases, but you boasted (you
    like boasting) that it did for the "hat" version of H, AKA P above. It
    does not. P(P) halts but H(P, P) == 0. Boring.


    That you don't bother to pay attention to the details or are unable to understand the x86 language well enough to understand the details in no
    way negates the fact that H(P,P) does correctly decide that its input
    never halts. No one can possibly provide a rebuttal to this simply
    because it is true.

    --
    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)
  • From olcott@21:1/5 to Malcolm McLean on Thu Aug 19 09:14:03 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/19/2021 5:26 AM, Malcolm McLean wrote:
    On Wednesday, 18 August 2021 at 16:44:44 UTC+1, olcott wrote:
    On 8/18/2021 10:28 AM, Malcolm McLean wrote:
    On Wednesday, 18 August 2021 at 14:57:10 UTC+1, olcott wrote:

    H has no effect on the machine that it simulates until after its halt
    status decision has been made. This conclusively proves that H can
    ignore its in execution trace during its halt status analysis.

    Anyone disagreeing with this is either not intelligent or knowledgeable >>>> enough to understand it, or a liar.

    That H does effect the behavior or its input at some other point is
    utterly irrelevant to this analysis. We are only answering the single
    question: Is it correct for H to ignore its own execution trace during >>>> its halt status analysis?

    If H is analysing H, it can't ignore the behaviour of H. That's why your results
    are wrong despite the execution trace seeming to show a non-halting
    behaviour.

    Because H only acts as a pure simulator of its input until after
    its halt status decision has been made it has no behavior that
    can possibly effect the behavior of its input. Because of this H
    screens out its own address range in every execution trace that
    it examines. This is why we never see any instructions of H in
    any execution trace after an input calls H.

    The above proves itself true entirely on the basis of the meaning
    of its words. There is no possible correct rebuttal there is only
    a failure to comprehend. If you believe that there is a correct
    rebuttal please provide it and I will point out your error.

    You're wrong here. When H is being called on a program which includes
    a call to H, the nested call to H needs to be analysed like any other
    call. It can and in fact does affect the halting behaviour of the input.

    You are doing as bad of a job analyzing this as Robert. You are making
    sure to simply ignore key words that I have said.

    WHILE H IS MAKING ITS HALT DECISION H IS ACTING AS A PURE SIMULATOR OF
    ITS INPUT.

    WHILE H IS ACTING AS A PURE SIMULATOR H CANNOT POSSIBLY HAVE ANY EFFECT
    ON THE BEHAVIOR OF ITS INPUT.

    WHILE H CANNOT POSSIBLY HAVE ANY EFFECT ON THE BEHAVIOR OF ITS INPUT H
    NEED NOT EXAMINE ITS OWN EXECUTION TRACE IN ITS HALT STATUS DECISION.

    Try and find a specific flaw in that, there are one.





    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Thu Aug 19 10:14:09 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/19/2021 8:14 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/18/2021 8:42 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/18/2021 8:16 PM, Ben Bacarisse wrote:

    Yes. I cut them because they are not the specification of the function >>>>> that I will challenge you to write.

    That is out-of-scope and you know it.

    Not in my opinion, no. A function that that shows there are undecidable >>> sets should worry you, but for some reason you prefer to stick with
    talking about your H that does something entirely unsurprising and
    uninteresting.

    So when I correctly refute the halting problem proofs you say no I did
    not refute every proof in the universe and the halting problem proof
    is one of these proofs therefore I did not refute the halting problem
    proof.

    No, I'm not saying that.

    Anyway, in case you are interested, here is the specification of the
    function you can't write:

    The computational model is C code with no memory restrictions. Of
    course, if you don't actually hit the memory limits of a C
    implementation it's just actual C code. I'd be happy to say more about
    this model of computation if you think the details will matter to your solution.

    The problem is that of deciding if a function would return if called
    from main. A "return decider" (in this model) is a C function returning _Bool that always returns a value to the expression in which it was
    called. A return decider always returns the same value for any
    arguments that represnet the same function call expression.

    Your mission, should you chose to accept it, is to write a return
    decider B with this prototype

    typedef uintptr_t data;
    typedef void (*function)(data);

    extern _Bool B(function, data);

    such that B(f, d) returns true if and only if a call of f from main with argument d returns to main. The two arguments, f and d, are said to represenet the call expression f(d).

    If, rather than just thinking you can do this, you have actual C code,
    you should provide either source or a compiled translation unit that can
    be linked with this one:

    #include <stdint.h>
    #include <stdio.h>

    typedef uintptr_t data;
    typedef void (*function)(data);

    extern _Bool B(function, data);

    void B_hat(data x) { if (B((function)x, x)) while (1); }

    int main(void)
    {
    printf("%d\n", B(B_hat, (data)B_hat));
    fflush(stdout);
    B_hat((data)B_hat);
    puts("returned");
    }

    The output should be either

    1
    returned

    or

    0

    with no further output. Of course you could always just agree that no
    such function B can be written.


    The x86utm operating system cannot call any C functions.
    Good job on the use of C. My own use of unsigned integers as function
    pointers is unconventional and not as portable. I did this on purpose so
    that x86utm would have a single standard tape element type.

    #include <stdint.h>
    #include <stdio.h>

    typedef uintptr_t data;
    typedef void (*function)(data);

    extern _Bool B(function, data);

    void B_hat(data x) { if (H((u32)x, (u32)x)) while (1); }

    int main2()
    {
    OutputHex(H((u32)B_hat, (u32)B_hat));
    B_hat((u32)B_hat);
    OutputString("returned");
    }


    _B_hat()
    [00000efc](01) 55 push ebp
    [00000efd](02) 8bec mov ebp,esp
    [00000eff](03) 8b4508 mov eax,[ebp+08]
    [00000f02](01) 50 push eax
    [00000f03](03) 8b4d08 mov ecx,[ebp+08]
    [00000f06](01) 51 push ecx
    [00000f07](05) e850feffff call 00000d5c
    [00000f0c](03) 83c408 add esp,+08
    [00000f0f](02) 85c0 test eax,eax
    [00000f11](02) 740b jz 00000f1e
    [00000f13](05) ba01000000 mov edx,00000001
    [00000f18](02) 85d2 test edx,edx
    [00000f1a](02) 7402 jz 00000f1e
    [00000f1c](02) ebf5 jmp 00000f13
    [00000f1e](01) 5d pop ebp
    [00000f1f](01) c3 ret
    Size in bytes:(0036) [00000f1f]

    _main2()
    [00000f2c](01) 55 push ebp
    [00000f2d](02) 8bec mov ebp,esp
    [00000f2f](05) 68fc0e0000 push 00000efc
    [00000f34](05) 68fc0e0000 push 00000efc
    [00000f39](05) e81efeffff call 00000d5c
    [00000f3e](03) 83c408 add esp,+08
    [00000f41](01) 50 push eax
    [00000f42](05) e8e5f3ffff call 0000032c
    [00000f47](03) 83c404 add esp,+04
    [00000f4a](05) 68fc0e0000 push 00000efc
    [00000f4f](05) e8a8ffffff call 00000efc
    [00000f54](03) 83c404 add esp,+04
    [00000f57](05) 6823030000 push 00000323
    [00000f5c](05) e8dbf3ffff call 0000033c
    [00000f61](03) 83c404 add esp,+04
    [00000f64](01) 5d pop ebp
    [00000f65](01) c3 ret
    Size in bytes:(0058) [00000f65]

    _main()
    [00000f6c](01) 55 push ebp
    [00000f6d](02) 8bec mov ebp,esp
    [00000f6f](05) e8b8ffffff call 00000f2c
    [00000f74](02) 33c0 xor eax,eax
    [00000f76](01) 5d pop ebp
    [00000f77](01) c3 ret
    Size in bytes:(0012) [00000f77]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= ...[00000f6c][00101c0a][00000000] 55 push ebp ...[00000f6d][00101c0a][00000000] 8bec mov ebp,esp ...[00000f6f][00101c06][00000f74] e8b8ffffff call 00000f2c ...[00000f2c][00101c02][00101c0a] 55 push ebp ...[00000f2d][00101c02][00101c0a] 8bec mov ebp,esp ...[00000f2f][00101bfe][00000efc] 68fc0e0000 push 00000efc ...[00000f34][00101bfa][00000efc] 68fc0e0000 push 00000efc ...[00000f39][00101bf6][00000f3e] e81efeffff call 00000d5c

    Begin Local Halt Decider Simulation at Machine Address:efc ...[00000efc][00211caa][00211cae] 55 push ebp ...[00000efd][00211caa][00211cae] 8bec mov ebp,esp ...[00000eff][00211caa][00211cae] 8b4508 mov eax,[ebp+08] ...[00000f02][00211ca6][00000efc] 50 push eax ...[00000f03][00211ca6][00000efc] 8b4d08 mov ecx,[ebp+08] ...[00000f06][00211ca2][00000efc] 51 push ecx ...[00000f07][00211c9e][00000f0c] e850feffff call 00000d5c ...[00000efc][0025c6d2][0025c6d6] 55 push ebp ...[00000efd][0025c6d2][0025c6d6] 8bec mov ebp,esp ...[00000eff][0025c6d2][0025c6d6] 8b4508 mov eax,[ebp+08] ...[00000f02][0025c6ce][00000efc] 50 push eax ...[00000f03][0025c6ce][00000efc] 8b4d08 mov ecx,[ebp+08] ...[00000f06][0025c6ca][00000efc] 51 push ecx ...[00000f07][0025c6c6][00000f0c] e850feffff call 00000d5c
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped ...[00000f3e][00101c02][00101c0a] 83c408 add esp,+08 ...[00000f41][00101bfe][00000000] 50 push eax ---[00000f42][00101bfe][00000000] e8e5f3ffff call 0000032c
    0
    ...[00000f47][00101c02][00101c0a] 83c404 add esp,+04 ...[00000f4a][00101bfe][00000efc] 68fc0e0000 push 00000efc ...[00000f4f][00101bfa][00000f54] e8a8ffffff call 00000efc ...[00000efc][00101bf6][00101c02] 55 push ebp ...[00000efd][00101bf6][00101c02] 8bec mov ebp,esp ...[00000eff][00101bf6][00101c02] 8b4508 mov eax,[ebp+08] ...[00000f02][00101bf2][00000efc] 50 push eax ...[00000f03][00101bf2][00000efc] 8b4d08 mov ecx,[ebp+08] ...[00000f06][00101bee][00000efc] 51 push ecx ...[00000f07][00101bea][00000f0c] e850feffff call 00000d5c

    Begin Local Halt Decider Simulation at Machine Address:efc ...[00000efc][0026c772][0026c776] 55 push ebp ...[00000efd][0026c772][0026c776] 8bec mov ebp,esp ...[00000eff][0026c772][0026c776] 8b4508 mov eax,[ebp+08] ...[00000f02][0026c76e][00000efc] 50 push eax ...[00000f03][0026c76e][00000efc] 8b4d08 mov ecx,[ebp+08] ...[00000f06][0026c76a][00000efc] 51 push ecx ...[00000f07][0026c766][00000f0c] e850feffff call 00000d5c ...[00000efc][002b719a][002b719e] 55 push ebp ...[00000efd][002b719a][002b719e] 8bec mov ebp,esp ...[00000eff][002b719a][002b719e] 8b4508 mov eax,[ebp+08] ...[00000f02][002b7196][00000efc] 50 push eax ...[00000f03][002b7196][00000efc] 8b4d08 mov ecx,[ebp+08] ...[00000f06][002b7192][00000efc] 51 push ecx ...[00000f07][002b718e][00000f0c] e850feffff call 00000d5c
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped ...[00000f0c][00101bf6][00101c02] 83c408 add esp,+08 ...[00000f0f][00101bf6][00101c02] 85c0 test eax,eax ...[00000f11][00101bf6][00101c02] 740b jz 00000f1e ...[00000f1e][00101bfa][00000f54] 5d pop ebp ...[00000f1f][00101bfe][00000efc] c3 ret ...[00000f54][00101c02][00101c0a] 83c404 add esp,+04 ...[00000f57][00101bfe][00000323] 6823030000 push 00000323 ---[00000f5c][00101bfe][00000323] e8dbf3ffff call 0000033c
    returned
    ...[00000f61][00101c02][00101c0a] 83c404 add esp,+04 ...[00000f64][00101c06][00000f74] 5d pop ebp ...[00000f65][00101c0a][00000000] c3 ret ...[00000f74][00101c0a][00000000] 33c0 xor eax,eax ...[00000f76][00101c0e][00100000] 5d pop ebp ...[00000f77][00101c12][00000008] c3 ret Number_of_User_Instructions(2)
    Number of Instructions Executed(47451)

    The paradox is that H does correctly decide that its simulation of
    _B_hat() on _B_hat() never halts and the execution of _B_hat() on
    _B_hat() does halt. This paradox is explained by the fact these two computations are not computationally equivalent to each other even
    though intuition would seem to say that they are.

    The key difference seems to be that there is a one-way dependency of
    _B_hat() on H that is not a mutual dependency. H is free to do as it
    chooses in deciding the halt status of its input. _B_hat() is a slave to whatever value that H returns.

    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    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

    Since it can be independently verified that H does correctly decide that
    its input will never stop running unless it aborts its simulation of
    this input we have met the halting problem burden of correctly deciding
    the halt status of the input description of a machine/program.

    The fact that the direct execution of P(P) halts does not contradict the
    fact that H(P,P) correctly decides that its input never halts because
    these two computations are not computationally equivalent.

    The key difference seems to be the dependency of the execution of P(P)
    on the return value of H(P,P) such that the execution of P(P) is a slave
    to whatever value that H(P,P) returns. There is no corresponding reverse dependency proving that these two computations are not computationally equivalent.

    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)
  • From olcott@21:1/5 to Malcolm McLean on Thu Aug 19 10:23:54 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/19/2021 9:39 AM, Malcolm McLean wrote:
    On Thursday, 19 August 2021 at 15:14:11 UTC+1, olcott wrote:
    On 8/19/2021 5:26 AM, Malcolm McLean wrote:
    On Wednesday, 18 August 2021 at 16:44:44 UTC+1, olcott wrote:
    On 8/18/2021 10:28 AM, Malcolm McLean wrote:
    On Wednesday, 18 August 2021 at 14:57:10 UTC+1, olcott wrote:

    H has no effect on the machine that it simulates until after its halt >>>>>> status decision has been made. This conclusively proves that H can >>>>>> ignore its in execution trace during its halt status analysis.

    Anyone disagreeing with this is either not intelligent or knowledgeable >>>>>> enough to understand it, or a liar.

    That H does effect the behavior or its input at some other point is >>>>>> utterly irrelevant to this analysis. We are only answering the single >>>>>> question: Is it correct for H to ignore its own execution trace during >>>>>> its halt status analysis?

    If H is analysing H, it can't ignore the behaviour of H. That's why your results
    are wrong despite the execution trace seeming to show a non-halting
    behaviour.

    Because H only acts as a pure simulator of its input until after
    its halt status decision has been made it has no behavior that
    can possibly effect the behavior of its input. Because of this H
    screens out its own address range in every execution trace that
    it examines. This is why we never see any instructions of H in
    any execution trace after an input calls H.

    The above proves itself true entirely on the basis of the meaning
    of its words. There is no possible correct rebuttal there is only
    a failure to comprehend. If you believe that there is a correct
    rebuttal please provide it and I will point out your error.

    You're wrong here. When H is being called on a program which includes
    a call to H, the nested call to H needs to be analysed like any other
    call. It can and in fact does affect the halting behaviour of the input.
    You are doing as bad of a job analyzing this as Robert. You are making
    sure to simply ignore key words that I have said.

    WHILE H IS MAKING ITS HALT DECISION H IS ACTING AS A PURE SIMULATOR OF
    ITS INPUT.

    WHILE H IS ACTING AS A PURE SIMULATOR H CANNOT POSSIBLY HAVE ANY EFFECT
    ON THE BEHAVIOR OF ITS INPUT.

    WHILE H CANNOT POSSIBLY HAVE ANY EFFECT ON THE BEHAVIOR OF ITS INPUT H
    NEED NOT EXAMINE ITS OWN EXECUTION TRACE IN ITS HALT STATUS DECISION.

    Try and find a specific flaw in that, there are one.

    Let's forget LInz and take this simple function

    void loopforever(U32 dummy)
    {
    while(1);
    }

    Now loopforever(dummy) doesn't halt, agreed?
    this function

    int H1(U32 dummy)
    {
    return H(loopforever, dummy);
    }

    halts and returns 0 (non-halting). Agreed?

    Now consider this function

    int H2(u32 dummy)
    {
    return H(H1, dummy);
    }

    What does that do?


    void Infinite_Loop()
    {
    HERE: goto HERE;
    }

    int main()
    {
    Output("Input_Halts = ", H0((u32)Infinite_Loop));
    }

    _Infinite_Loop()
    [00000ea2](01) 55 push ebp
    [00000ea3](02) 8bec mov ebp,esp
    [00000ea5](02) ebfe jmp 00000ea5
    [00000ea7](01) 5d pop ebp
    [00000ea8](01) c3 ret
    Size in bytes:(0007) [00000ea8]

    _main()
    [00000f02](01) 55 push ebp
    [00000f03](02) 8bec mov ebp,esp
    [00000f05](05) 68a20e0000 push 00000ea2
    [00000f0a](05) e8e3fcffff call 00000bf2
    [00000f0f](03) 83c404 add esp,+04
    [00000f12](01) 50 push eax
    [00000f13](05) 6823030000 push 00000323
    [00000f18](05) e835f4ffff call 00000352
    [00000f1d](03) 83c408 add esp,+08
    [00000f20](02) 33c0 xor eax,eax
    [00000f22](01) 5d pop ebp
    [00000f23](01) c3 ret
    Size in bytes:(0034) [00000f23]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= ...[00000f02][00101b56][00000000] 55 push ebp ...[00000f03][00101b56][00000000] 8bec mov ebp,esp ...[00000f05][00101b52][00000ea2] 68a20e0000 push 00000ea2 ...[00000f0a][00101b4e][00000f0f] e8e3fcffff call 00000bf2

    Begin Local Halt Decider Simulation at Machine Address:ea2 ...[00000ea2][00211bfa][00211bfe] 55 push ebp ...[00000ea3][00211bfa][00211bfe] 8bec mov ebp,esp ...[00000ea5][00211bfa][00211bfe] ebfe jmp 00000ea5 ...[00000ea5][00211bfa][00211bfe] ebfe jmp 00000ea5
    Local Halt Decider: Infinite Loop Detected Simulation Stopped

    ...[00000f0f][00101b56][00000000] 83c404 add esp,+04 ...[00000f12][00101b52][00000000] 50 push eax ...[00000f13][00101b4e][00000323] 6823030000 push 00000323 ---[00000f18][00101b4e][00000323] e835f4ffff call 00000352
    Input_Halts = 0
    ...[00000f1d][00101b56][00000000] 83c408 add esp,+08 ...[00000f20][00101b56][00000000] 33c0 xor eax,eax ...[00000f22][00101b5a][00100000] 5d pop ebp ...[00000f23][00101b5e][00000004] c3 ret Number_of_User_Instructions(1)
    Number of Instructions Executed(627)



    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Thu Aug 19 18:50:31 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/19/2021 6:14 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Ĥ applied to ⟨Ĥ⟩ halts.

    Yes.

    And on the 12th Aug you said, and I quote

    "⟨Ĥ⟩ ⟨Ĥ⟩ is not a string that encodes a halting computation."

    This is incorrect. You need to correct that statement so you can go on
    to investigate the consequences. It's not a trivial error. It's
    absolutely central to the case under investigation.

    You are saying that Ĥ applied to ⟨Ĥ⟩ halts.

    We are both saying that -- you said it above and of course I agree. The point of disagreement is that you said

    "⟨Ĥ⟩ ⟨Ĥ⟩ is not a string that encodes a halting computation."

    which is false. ⟨Ĥ⟩ ⟨Ĥ⟩ /is/ a string that encodes a halting computation.

    I am saying that the input to Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ never halts.

    I know you are. That may or may not mean the same as "⟨Ĥ⟩ ⟨Ĥ⟩ is not a
    string that encodes a halting computation" (I think its does mean the
    same, just poorly worded), but obviously I want to correct the clear and unambiguously wrong version from Aug 12th. So long as you refuse to
    accept that ⟨Ĥ⟩ ⟨Ĥ⟩ is a string that encodes a halting computation, discussion is pointless.


    You say that it encodes a halting computation because Ĥ applied to ⟨Ĥ⟩ halts yet this simply ignores that fact that the input to Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩
    never halts.

    Because of the pathological self-reference that Flibble objected to
    exists whether or not ⟨Ĥ⟩ ⟨Ĥ⟩ encodes a halting computation depends on
    its placement in the execution trace.

    If Ĥ is applied to ⟨Ĥ⟩ at the beginning of the execution trace then this Ĥ halts because of its dependency on the other instances at Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩.

    The inputs to Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ have no such dependency thus specify an entirely different computation.


    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Fri Aug 20 11:44:51 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/20/2021 11:36 AM, Ben Bacarisse wrote:
    Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

    On Friday, 20 August 2021 at 16:31:33 UTC+1, olcott wrote:
    On 8/20/2021 10:10 AM, Ben Bacarisse wrote:

    You are not going to stay focused on the most serious error you have yet >>>> posted?
    You have to go though the following reasoning and point out the specific >>> error. Making a blanket assertion that there is an error somewhere does
    not count as any rebuttal at all.
    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

    The first (executed) Ĥ has a dependency on these two (simulated) ⟨Ĥ⟩ ⟨Ĥ⟩
    that do not have a dependency on the first Ĥ, this makes their position >>> in the execution trace have an effect on their behavior.

    Perhaps this is simply beyond your capacity to understand?

    From this we can conclude that while the simulating halt decider at
    Ĥ.qx remains in pure simulation mode (thus not aborting the simulation
    of its input) Ĥ applied to ⟨Ĥ⟩ never halts.

    You need to start by agreeing that ⟨Ĥ⟩ ⟨Ĥ⟩ is a string that encodes a
    halting computation.
    You have to find the specific error in my rebuttal of this. Making a
    blanket assertion that there is an error somewhere does not count as any >>> rebuttal at all.

    H_Hat(H_Hat) halts, whilst H(H_Hat, H_Hat) returns false (non-halting).

    H gets H_Hat wrong, as Linz says it must do. No surprise there.

    The surprise is that the "execution trace" seems to show H_Hat(H_Hat) as
    non halting as well.

    At least one trace, explicitly of H_Hat(H_Hat), shows it halting. And
    when PO pretended that his H might meet the specification I gave for B
    (a "function return decider") it showed B_hat(B_hat) returning after a separate top-level call to B(B_hat, B_hat) returned 0.


    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    In order to show that the above definition has been satisfied we only
    have to show that halt decider Ĥ.qx does correctly decide whether or not
    its input description ⟨Ĥ1⟩ of a Turing machine would halt on its input ⟨Ĥ2⟩.

    // ⟨Ĥ1⟩ Input to Ĥ
    // ⟨Ĥ2⟩ Copy of ⟨Ĥ1⟩ input to

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if ⟨Ĥ1⟩ applied to ⟨Ĥ1⟩ halts, and Ĥ

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    When we define Ĵ to be exactly like Ĥ except that it has a UTM at Ĵ.qx instead of a simulating halt decider then we can see that Ĵ applied to ⟨Ĵ⟩ never halts.

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    From this we can conclude that while the simulating halt decider at
    Ĥ.qx remains in pure simulation mode (thus not aborting the simulation
    of its input) ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ never halts.
    Key halt deciding theorem that applies to every simulating halt decider
    (SHD):
    (a) Every input to a SHD that never stops running unless its simulation
    is aborted, or
    (b) Every input that never stops running while the SHD is in pure
    simulation mode.
    Is an input that is correctly decided as never halting.


    --
    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)
  • From olcott@21:1/5 to Malcolm McLean on Fri Aug 20 11:42:07 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/20/2021 10:45 AM, Malcolm McLean wrote:
    On Friday, 20 August 2021 at 16:31:33 UTC+1, olcott wrote:
    On 8/20/2021 10:10 AM, Ben Bacarisse wrote:

    You are not going to stay focused on the most serious error you have yet >>> posted?
    You have to go though the following reasoning and point out the specific
    error. Making a blanket assertion that there is an error somewhere does
    not count as any rebuttal at all.
    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

    The first (executed) Ĥ has a dependency on these two (simulated) ⟨Ĥ⟩ ⟨Ĥ⟩
    that do not have a dependency on the first Ĥ, this makes their position
    in the execution trace have an effect on their behavior.

    Perhaps this is simply beyond your capacity to understand?

    From this we can conclude that while the simulating halt decider at
    Ĥ.qx remains in pure simulation mode (thus not aborting the simulation
    of its input) Ĥ applied to ⟨Ĥ⟩ never halts.

    You need to start by agreeing that ⟨Ĥ⟩ ⟨Ĥ⟩ is a string that encodes a
    halting computation.
    You have to find the specific error in my rebuttal of this. Making a
    blanket assertion that there is an error somewhere does not count as any
    rebuttal at all.

    H_Hat(H_Hat) halts, whilst H(H_Hat, H_Hat) returns false (non-halting).

    H gets H_Hat wrong, as Linz says it must do. No surprise there.
    the Turing machine halting problem. Simply stated, the problem
    is: given the description of a Turing machine M and an input w,
    does M, when started in the initial configuration q0w, perform a
    computation that eventually halts? (Linz:1990:317).

    In order to show that the above definition has been satisfied we only
    have to show that halt decider Ĥ.qx does correctly decide whether or not
    its input description ⟨Ĥ1⟩ of a Turing machine would halt on its input ⟨Ĥ2⟩.

    // ⟨Ĥ1⟩ Input to Ĥ
    // ⟨Ĥ2⟩ Copy of ⟨Ĥ1⟩ input to

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and Ĥ

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    When we define Ĵ to be exactly like Ĥ except that it has a UTM at Ĵ.qx instead of a simulating halt decider then we can see that Ĵ applied to ⟨Ĵ⟩ never halts.

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    From this we can conclude that while the simulating halt decider at
    Ĥ.qx remains in pure simulation mode (thus not aborting the simulation
    of its input) ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ never halts.

    Key halt deciding theorem that applies to every simulating halt decider
    (SHD):
    (a) Every input to a SHD that never stops running unless its simulation
    is aborted, or
    (b) Every input that never stops running while the SHD is in pure
    simulation mode.
    Is an input that is correctly decided as never halting.

    The surprise is that the "execution trace" seems to show H_Hat(H_Hat) as
    non halting as well. So did H_Hat(H_Hat) not halt all along, and we are too sinful to see it? Or is there something wrong with the execution trace?

    Obviously the only sane conclusion anyone can draw is that there is something wrong with the execution trace. So exactly what? If a function's position in the
    execution trace has an effect on its behaviour, this suggests what might be wrong.
    But whilst people can and have made sensible, informed guesses as to what is wrong, you're either unwilling or unable to answer some pretty basic questions
    about H. So it remains a conjecture.



    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Fri Aug 20 16:09:31 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/20/2021 3:40 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/20/2021 10:10 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    I am not going to bother to answer all of this so that you can stay
    focused on one key point:

    You are not going to stay focused on the most serious error you have yet >>> posted?

    You have to go though the following reasoning and point out the
    specific error.

    The specific error is that the string ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the computation of
    Ĥ applied to ⟨Ĥ⟩ which, everyone agrees, is a halting computation. Your
    statement of Aug 12th that

    "⟨Ĥ⟩ ⟨Ĥ⟩ is not a string that encodes a halting computation."

    is simply wrong in the simplest factual way. I don't have to look
    anywhere else to point out the specific error.


    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    The executed Ĥ in the above expression only halts because of its
    computational dependence on the halt status decision of the simulating
    halt decider on its input Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩.

    The simulated input Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ has no such computational dependence
    on the executed Ĥ.

    That the computational dependence of one computation on other
    conclusively proves that the dependent computation is not
    computationally equivalent to the independent computation may be beyond
    your capacity to understand.

    None-the-less the paradox is finally resolved.

    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Fri Aug 20 16:20:44 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/20/2021 3:58 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/20/2021 3:32 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    // ⟨Ĥ1⟩ Input to Ĥ
    // ⟨Ĥ2⟩ Copy of ⟨Ĥ1⟩ input to

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if ⟨Ĥ1⟩ applied to ⟨Ĥ1⟩ halts, and Ĥ

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    Pure poetry. What does it mean to apply a string to a string? And all
    the ⟨Ĥi⟩ are identical to each other (and to ⟨Ĥ⟩) so I can write this as

    Ĥ.q0 ⟨Ĥ2⟩ ⊢* Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ1⟩ ⊢* Ĥ.qn
    if ⟨Ĥ2⟩ applied to ⟨Ĥ1⟩ does not halt

    and it must mean exactly the same thing. You really have no idea how to >>> use any mathematical notation.

    The point is that you are simply ignoring the dependency that the
    executed Ĥ has on the status decision of the simulated inputs to Ĥ.qx
    ⟨Ĥ1⟩ ⟨Ĥ2⟩.

    I am pointing out that your notation above is silly and meaningless. Of course you will be wrong about other things as well, but wouldn't it be useful to correct things one step at a time? The six supposedly clear symbolic lines above contain numerous errors.


    My notion seems to be silly and meaningless in the same way that
    calculus would seem silly and meaningless to a two year old. There was a
    very smart four year old that could perform calculus quite well.

    void P2(u32 x)
    {
    if (H1(x, x))
    HERE: goto HERE;
    }

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

    Even though H1 has identical machine code to H the fact that H(P,P) has
    a dependency on the halt status decision of H1(P,P) whereas H1(P,P) has
    no such dependency proves that H(P,P) and H1(P,P) are distinctly
    different computations that can have different behavior without
    contradiction.

    Because H1 has identical machine code to H and the input to both of
    these instances is the same the fact that they derive different results conclusively proves that an identical function with the same input can
    derive a different results when one function has computational
    dependence on the other identical function.

    _P2()
    [00000e52](01) 55 push ebp
    [00000e53](02) 8bec mov ebp,esp
    [00000e55](03) 8b4508 mov eax,[ebp+08]
    [00000e58](01) 50 push eax
    [00000e59](03) 8b4d08 mov ecx,[ebp+08]
    [00000e5c](01) 51 push ecx
    [00000e5d](05) e8b0fcffff call 00000b12 // call H1
    [00000e62](03) 83c408 add esp,+08
    [00000e65](02) 85c0 test eax,eax
    [00000e67](02) 7402 jz 00000e6b
    [00000e69](02) ebfe jmp 00000e69
    [00000e6b](01) 5d pop ebp
    [00000e6c](01) c3 ret
    Size in bytes:(0027) [00000e6c]

    _main()
    [00000e72](01) 55 push ebp
    [00000e73](02) 8bec mov ebp,esp
    [00000e75](05) 68520e0000 push 00000e52 // push P2
    [00000e7a](05) 68520e0000 push 00000e52 // push P2
    [00000e7f](05) e84efeffff call 00000cd2 // call H
    [00000e84](03) 83c408 add esp,+08
    [00000e87](01) 50 push eax
    [00000e88](05) 6823030000 push 00000323
    [00000e8d](05) e8c0f4ffff call 00000352
    [00000e92](03) 83c408 add esp,+08
    [00000e95](02) 33c0 xor eax,eax
    [00000e97](01) 5d pop ebp
    [00000e98](01) c3 ret
    Size in bytes:(0039) [00000e98]

    machine stack stack machine assembly
    address address data code language
    ======== ======== ======== ========= ============= ...[00000e72][00101a94][00000000] 55 push ebp ...[00000e73][00101a94][00000000] 8bec mov ebp,esp ...[00000e75][00101a90][00000e52] 68520e0000 push 00000e52 // push P2 ...[00000e7a][00101a8c][00000e52] 68520e0000 push 00000e52 // push P2 ...[00000e7f][00101a88][00000e84] e84efeffff call 00000cd2 // call H

    Begin Local Halt Decider Simulation at Machine Address:e52 ...[00000e52][00211b34][00211b38] 55 push ebp ...[00000e53][00211b34][00211b38] 8bec mov ebp,esp ...[00000e55][00211b34][00211b38] 8b4508 mov eax,[ebp+08] ...[00000e58][00211b30][00000e52] 50 push eax // push P2 ...[00000e59][00211b30][00000e52] 8b4d08 mov ecx,[ebp+08] ...[00000e5c][00211b2c][00000e52] 51 push ecx // push P2 ...[00000e5d][00211b28][00000e62] e8b0fcffff call 00000b12 // call H1

    Begin Local Halt Decider Simulation at Machine Address:e52 ...[00000e52][0025c55c][0025c560] 55 push ebp ...[00000e53][0025c55c][0025c560] 8bec mov ebp,esp ...[00000e55][0025c55c][0025c560] 8b4508 mov eax,[ebp+08] ...[00000e58][0025c558][00000e52] 50 push eax // push P2 ...[00000e59][0025c558][00000e52] 8b4d08 mov ecx,[ebp+08] ...[00000e5c][0025c554][00000e52] 51 push ecx // push P2 ...[00000e5d][0025c550][00000e62] e8b0fcffff call 00000b12 // call H1 ...[00000e52][002a6f84][002a6f88] 55 push ebp ...[00000e53][002a6f84][002a6f88] 8bec mov ebp,esp ...[00000e55][002a6f84][002a6f88] 8b4508 mov eax,[ebp+08] ...[00000e58][002a6f80][00000e52] 50 push eax // push P2 ...[00000e59][002a6f80][00000e52] 8b4d08 mov ecx,[ebp+08] ...[00000e5c][002a6f7c][00000e52] 51 push ecx // push P2 ...[00000e5d][002a6f78][00000e62] e8b0fcffff call 00000b12 // call H1
    Local Halt Decider: Infinite Recursion Detected Simulation Stopped

    ...[00000e62][00211b34][00211b38] 83c408 add esp,+08 ...[00000e65][00211b34][00211b38] 85c0 test eax,eax ...[00000e67][00211b34][00211b38] 7402 jz 00000e6b ...[00000e6b][00211b38][00000d8f] 5d pop ebp ...[00000e6c][00211b3c][00000e52] c3 ret ...[00000e84][00101a94][00000000] 83c408 add esp,+08 ...[00000e87][00101a90][00000001] 50 push eax ...[00000e88][00101a8c][00000323] 6823030000 push 00000323 ---[00000e8d][00101a8c][00000323] e8c0f4ffff call 00000352
    Input_Halts = 1
    ...[00000e92][00101a94][00000000] 83c408 add esp,+08 ...[00000e95][00101a94][00000000] 33c0 xor eax,eax ...[00000e97][00101a98][00100000] 5d pop ebp ...[00000e98][00101a9c][00000004] c3 ret Number_of_User_Instructions(1)
    Number of Instructions Executed(617658)

    Even though H1 has identical machine code to H the fact that H(P,P) has
    a dependency on the halt status decision of H1(P,P) whereas H1(P,P) has
    no such dependency proves that H(P,P) and H1(P,P) are 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)
  • From olcott@21:1/5 to Ben Bacarisse on Sat Aug 21 23:01:42 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/21/2021 8:27 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/21/2021 6:14 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    It is trivially easy for me to understand that the simulation of ⟨Ĥ1⟩ >>>> ⟨Ĥ2⟩ by the simulating halt decider at Ĥ.qx never stops running unless
    this SHD aborts its simulation of ⟨Ĥ1⟩ ⟨Ĥ2⟩.

    You are reduced to saying things not in dispute as if they change any of >>> the facts you are wrong about.

    You never agreed to this before.

    Don't be silly. I even gave this problem a name: "PO's Other Halting" problem. You remember the POOH problem? What happens "unless" (rather
    than what actually happens) is the same silly ruse you've been pulling
    for years.

    Now we apply this Theorem:
    Simulating Halt Decider Theorem (Olcott 2020):
    A simulating halt decider correctly decides that any input that never
    halts unless the simulating halt decider aborts its simulation of this
    input is an input that never halts.

    This is not a theorem but the definition of what "correct" means for the
    POOH problem. A problem no one else cares about.


    You have already agreed to it:

    On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Truism:
    Every simulation that would never stop unless Halts() stops
    it at some point specifies infinite execution.

    Any algorithm that implements this truism is, of course, a halting
    decider.




    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Sun Aug 22 11:49:22 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/22/2021 9:45 AM, Ben Bacarisse wrote:
    Richard Damon <Richard@Damon-Family.org> writes:

    On 8/22/21 12:01 AM, olcott wrote:
    On 8/21/2021 8:27 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/21/2021 6:14 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    It is trivially easy for me to understand that the simulation of ⟨Ĥ1⟩
    ⟨Ĥ2⟩ by the simulating halt decider at Ĥ.qx never stops running unless
    this SHD aborts its simulation of ⟨Ĥ1⟩ ⟨Ĥ2⟩.

    You are reduced to saying things not in dispute as if they change
    any of
    the facts you are wrong about.

    You never agreed to this before.

    Don't be silly.  I even gave this problem a name: "PO's Other Halting" >>>> problem.  You remember the POOH problem?  What happens "unless" (rather >>>> than what actually happens) is the same silly ruse you've been pulling >>>> for years.

    Now we apply this Theorem:
    Simulating Halt Decider Theorem (Olcott 2020):
    A simulating halt decider correctly decides that any input that never >>>>> halts unless the simulating halt decider aborts its simulation of this >>>>> input is an input that never halts.

    This is not a theorem but the definition of what "correct" means for the >>>> POOH problem.  A problem no one else cares about.


    You have already agreed to it:

    On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Truism:
    Every simulation that would never stop unless Halts() stops
    it at some point specifies infinite execution.

    Any algorithm that implements this truism is, of course, a halting
    decider.

    I think you just got him too confused at some point and he made a
    misstatement. You abuse the language enough that this is quite
    possible.

    Excuse me! I was not at all confused. Something is lost by removing
    the context (and the rest if the paragraph that PO cuts helps to make
    the meaning clearer) but any algorithm that can decide that a simulation would never stop is a halt decider. The irony is that if he uses that algorithm to turn the simulator into a partial one, the result is not a
    halt decider!

    I don't really know what PO thinks I meant by these words, but since you
    are sane and knowledgeable and you think I made a mistake, my words can obviously be misunderstood. What did you think I was saying?


    While a simulating halt decider is in simulation mode it cannot possibly
    have any effect on the behavior of its input. While it cannot possibly
    have any effect on the behavior of its input it is computationally
    equivalent to a pure simulator's effect on the behavior of its input.

    While a simulating halt decider is computationally equivalent to a pure simulator and this simulation would never stop unless it stops it at
    some point we can know that this input specifies infinite execution.

    There may be some double-talk "rebuttal" that will fool the ignorant and gullible if you try hard enough. The ignorant and gullible are not in my
    target audience.



    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Sun Aug 22 12:18:44 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/22/2021 11:14 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/22/2021 9:34 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/21/2021 8:27 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/21/2021 6:14 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    It is trivially easy for me to understand that the simulation of ⟨Ĥ1⟩
    ⟨Ĥ2⟩ by the simulating halt decider at Ĥ.qx never stops running unless
    this SHD aborts its simulation of ⟨Ĥ1⟩ ⟨Ĥ2⟩.

    You are reduced to saying things not in dispute as if they change any of
    the facts you are wrong about.

    You never agreed to this before.
    Don't be silly. I even gave this problem a name: "PO's Other Halting" >>>>> problem. You remember the POOH problem? What happens "unless" (rather >>>>> than what actually happens) is the same silly ruse you've been pulling >>>>> for years.

    Now we apply this Theorem:
    Simulating Halt Decider Theorem (Olcott 2020):
    A simulating halt decider correctly decides that any input that never >>>>>> halts unless the simulating halt decider aborts its simulation of this >>>>>> input is an input that never halts.

    This is not a theorem but the definition of what "correct" means for the >>>>> POOH problem. A problem no one else cares about.

    You have already agreed to it:
    Yes, I have agreed that you get to define what the correct answer is for >>> any instance of the POOH problem. The wold continues to spin and no one >>> gives a flying fig about it.

    On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Truism:
    Every simulation that would never stop unless Halts() stops
    it at some point specifies infinite execution.

    Any algorithm that implements this truism is, of course, a halting
    decider.
    I find your endless quoting of this peculiar because you disagree with
    it! You adamantly state that you don't have a halt decider (as I and
    the world defines is). Are your really saying that you have such an
    algorithm? We know you have a partial POOH decider, but that's not what >>> I mean when I talk of a halt decider.

    No comment of course on your mistake. It's too serious and too obvious
    to do anything but deflect attention from it. Your "⟨Ĥ⟩ ⟨Ĥ⟩ does not
    encode a halting computation" can not be justified.

    It is justified on the basis that it meets the
    Simulating Halt Decider Theorem (Olcott 2020)
    non halting criteria that you agreed to.

    But not on the basis of what a halt decider is.


    You already agreed that it <is> a halting decider, any reversal on this
    can only be construed as deception.

    a. The string ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the computation of your Ĥ applied to ⟨Ĥ⟩.
    b. Your Ĥ applied to ⟨Ĥ⟩ halts.
    c. Your H rejects the string ⟨Ĥ⟩ ⟨Ĥ⟩ when it should accept it.


    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    The difference in the behavior of the Ĥ at the beginning of the above
    template and the behavior of the input to Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ is accounted
    for by the fact that these are distinctly different computations that
    are not computationally equivalent.

    This is much more easily understood by the H(P,P) model where every
    detail is explicitly specified and no details are left to the
    imagination. The very preliminary very rough draft of this analysis is currently on page 7 of this paper.

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


    The basic idea that two distinctly different computations are not
    required to have the same behavior is very obviously correct common
    knowledge.

    The analysis of how these intuitively identical computations are
    actually distinctly different is the only difficult aspect of this. The verified fact that their correct x86 execution trace is not the same conclusively proves that they are distinctly different computations,
    thus can have different behavior without contradiction.

    The same function with the same input must derive identical results or
    the results are not a pure function of its inputs.

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    In the above computation the computational distinction between Ĥ.qx that transitions to its final state of Ĥ.qn and its input ⟨Ĥ1⟩ ⟨Ĥ2⟩ that never transitions to any final state is that the execution of Ĥ.qx is
    the outer-most instance of what would otherwise be an infinite set of
    nested simulations.

    It is the only instance of Ĥ.qx that is not under the dominion of
    another instance of Ĥ.qx. This makes this outermost instance
    computationally distinct from the inner instances.

    Are you going to try to doubletalk your way out of that one?

    It would be a waste of everyone's time but would serve you well as a distraction from a, b and c. What matters (or should matter to you) is
    that you are obviously wrong. That remains true even if I were to agree
    with everything you have ever said.



    --
    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)
  • From olcott@21:1/5 to olcott on Sun Aug 22 13:32:48 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/22/2021 12:18 PM, olcott wrote:
    On 8/22/2021 11:14 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/22/2021 9:34 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/21/2021 8:27 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/21/2021 6:14 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    It is trivially easy for me to understand that the simulation >>>>>>>>> of ⟨Ĥ1⟩
    ⟨Ĥ2⟩ by the simulating halt decider at Ĥ.qx never stops running >>>>>>>>> unless
    this SHD aborts its simulation of ⟨Ĥ1⟩ ⟨Ĥ2⟩.

    You are reduced to saying things not in dispute as if they
    change any of
    the facts you are wrong about.

    You never agreed to this before.
    Don't be silly.  I even gave this problem a name: "PO's Other
    Halting"
    problem.  You remember the POOH problem?  What happens "unless"
    (rather
    than what actually happens) is the same silly ruse you've been
    pulling
    for years.

    Now we apply this Theorem:
    Simulating Halt Decider Theorem (Olcott 2020):
    A simulating halt decider correctly decides that any input that
    never
    halts unless the simulating halt decider aborts its simulation of >>>>>>> this
    input is an input that never halts.

    This is not a theorem but the definition of what "correct" means
    for the
    POOH problem.  A problem no one else cares about.

    You have already agreed to it:
    Yes, I have agreed that you get to define what the correct answer is
    for
    any instance of the POOH problem.  The wold continues to spin and no
    one
    gives a flying fig about it.

    On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Truism:
    Every simulation that would never stop unless Halts() stops
    it at some point specifies infinite execution.

    Any algorithm that implements this truism is, of course, a halting >>>>>> decider.
    I find your endless quoting of this peculiar because you disagree with >>>> it!  You adamantly state that you don't have a halt decider (as I and >>>> the world defines is).  Are your really saying that you have such an
    algorithm?  We know you have a partial POOH decider, but that's not
    what
    I mean when I talk of a halt decider.

    No comment of course on your mistake.  It's too serious and too obvious >>>> to do anything but deflect attention from it.  Your "⟨Ĥ⟩ ⟨Ĥ⟩ does not
    encode a halting computation" can not be justified.

    It is justified on the basis that it meets the
    Simulating Halt Decider Theorem (Olcott 2020)
    non halting criteria that you agreed to.

    But not on the basis of what a halt decider is.


    You already agreed that it <is> a halting decider, any reversal on this
    can only be construed as deception.

    a. The string ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the computation of your Ĥ applied to ⟨Ĥ⟩.
    b. Your Ĥ applied to ⟨Ĥ⟩ halts.
    c. Your H rejects the string ⟨Ĥ⟩ ⟨Ĥ⟩ when it should accept it.


    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    The difference in the behavior of the Ĥ at the beginning of the above template and the behavior of the input to Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ is accounted
    for by the fact that these are distinctly different computations that
    are not computationally equivalent.

    This is much more easily understood by the H(P,P) model where every
    detail is explicitly specified and no details are left to the
    imagination. The very preliminary very rough draft of this analysis is currently on page 7 of this paper.

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


    The basic idea that two distinctly different computations are not
    required to have the same behavior is very obviously correct common knowledge.

    The analysis of how these intuitively identical computations are
    actually distinctly different is the only difficult aspect of this. The verified fact that their correct x86 execution trace is not the same conclusively proves that they are distinctly different computations,
    thus can have different behavior without contradiction.

    The same function with the same input must derive identical results or
    the results are not a pure function of its inputs.

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    In the above computation the computational distinction between Ĥ.qx that transitions to its final state of Ĥ.qn and its input ⟨Ĥ1⟩ ⟨Ĥ2⟩ that
    never transitions to any final state is that the execution of Ĥ.qx is
    the outer-most instance of what would otherwise be an infinite set of
    nested simulations.

    It is the only instance of Ĥ.qx that is not under the dominion of
    another instance of Ĥ.qx. This makes this outermost instance
    computationally distinct from the inner instances.


    The executed instances of H(P,P) are distinctly different computations
    than the simulated instances in that the executed instances are not
    under the dominion of a halt decider. It is this difference that enables
    them to have different behavior.

    // 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((u32)P);
    }


    Are you going to try to doubletalk your way out of that one?

    It would be a waste of everyone's time but would serve you well as a
    distraction from a, b and c.  What matters (or should matter to you) is
    that you are obviously wrong.  That remains true even if I were to agree
    with everything you have ever said.





    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Sun Aug 22 15:06:03 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/22/2021 2:46 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:
    (anything to avoid addressing the incontrovertible facts)

    On 8/22/2021 2:00 PM, Ben Bacarisse wrote:

    a. The string ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the computation of your Ĥ applied to ⟨Ĥ⟩.
    b. Your Ĥ applied to ⟨Ĥ⟩ halts.
    c. Your H rejects the string ⟨Ĥ⟩ ⟨Ĥ⟩ when it should accept it. >>>
    I take it you agree with a, b and c since you make no comment about
    them. If you do not agree, you need to say which ones you disagree
    with.

    You have not said which of a, b or c you deny. I don't want to put
    words in your mouth (what sort of person would do that, eh?) but I will
    have to assume you agree with them all if you don't say.


    As I have already explained in complete detail your simplistic analysis conflates together two distinctly different computations:
    (1) Executed Ĥ applied to ⟨Ĥ⟩ // can't be aborted

    (2) Simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ by a simulating halt decider
    // can be and is aborted.

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    The execution of Ĥ is computationally distinct from the simulation of ⟨Ĥ1⟩ ⟨Ĥ2⟩ by the simulating halt decider at Ĥ.qx so the fact that Ĥ.qx
    transitions to its final state of Ĥ.qn does not contradict the fact that
    Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ correctly decides that its input never halts.

    THIS SEEMS BEYOND YOUR CAPACITY TO COMPREHEND:
    The executed instances of Ĥ are not under the dominion of a simulating
    halt decider that can abort them before they get started. This
    conclusively proves that they can have different behavior without
    forming any 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)
  • From olcott@21:1/5 to Malcolm McLean on Mon Aug 23 13:32:28 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/23/2021 12:58 PM, Malcolm McLean wrote:
    On Monday, 23 August 2021 at 16:01:23 UTC+1, olcott wrote:
    On 8/23/2021 9:43 AM, Malcolm McLean wrote:

    So that's the crux of it. If you say that the behaviour of the function (C usage)
    can change based on its execution environment, you are no longer in the world of
    so-called "pure" mathematical functions.

    It might superficially seem that way only because the concept of a
    simulating halt decider is new and has not been extensively studied.

    No one serious is interested in halt deciders for the same reason that no-one serious
    is interested in perpetual motion machines. If it is known that something cannot be
    achieved, you don't waste time on things that might look superficially as if they
    are getting there.

    void Infinite_Loop()
    {
    HERE: goto HERE;
    }

    It is very obvious that the behavior the direct execution of the above
    computation must be different than the behavior of the simulation of
    this same computation under the dominion of a simulating halt decider.

    It is also quite obvious that the simulating halt decider does correctly
    decide that Infinite_Loop() never halts.

    So we agree that Infinite_Loop() is a computation, and never halts. H(Infinite_Loop), with whatever twiddles we need for the unused arguments,
    is also a computation. It halts and returns false.

    So that's a good basis to work from.


    This conclusively proves that the direct execution of a machine is not computationally equivalent to the simulation of the machine description
    of this machine by a simulating halt decider when this machine never halts.

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    From this we can conclude that the fact that Ĥ.qx transitions to its
    final state of Ĥ.qn and halts does not contradict the fact that Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ did correctly decide that its input never halts.

    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)
  • From olcott@21:1/5 to Ben Bacarisse on Mon Aug 23 14:51:51 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/23/2021 2:30 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/23/2021 8:16 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    When a computation is forced to stop running this is an entirely
    different thing than a computation that stops running because it is
    has completed all of its steps. If we allow this ambiguity to remain
    then disingenuous double talk seems more plausible.
    How is a TM "forced" to do anything?

    You aready know this,

    Nope. I have no idea. TM's halt or they don't and they are never
    forced to do anything. You don't really know what it means either or
    you would have addressed the question of what it means seriously.

    you are merely being tediously nit picky about my choice of words.

    As any journal editor or article reviewer would be. Be assured that I
    am being very generous is the errors I /don't/ pick up on. Your vague
    and undefined words will be absolutely shredded by anyone who has to
    read a paper should you ever think you can write one.

    On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Truism:
    Every simulation that would never stop unless Halts() stops
    it at some point specifies infinite execution.

    Any algorithm that implements this truism is, of course, a halting
    decider.

    You must be an atheist because a Christian knows the penalty for
    lying.

    You still won't answer my question will you? Avoid, avoid, avoid! You
    quote me approvingly -- does that mean you have changed your mind and
    you are now claiming to have an algorithm that decides halting (in
    general)? You have studiously avoided making that claim so far.


    Whether or not I have an algorithm that correctly decides halting for
    all inputs is a dishonest dodge away from the point at hand.

    The point at hand is that when the above criteria is used by a partial
    halt decider to decide the conventional halting problem counter-examples
    then it does correctly decide that these counter-examples never halt.

    This is, despite the absurdity, a serious question. If I gave you a TM
    and an input, how could you tell the difference between it simply
    halting ("completing all of its steps") and being "forced to stop
    running"? If you can't do that (and I know you can't), you should be
    able to show me two TM computations, one which just halts and one which
    is forced to stop.

    When any x86/TM machine...

    We are talking about TMs. You probably don't know what your words games
    mean anymore than I do which is why you avoided the question. (Avoid,
    avoid, avoid!)


    I ignore dishonest dodges away from the point at hand.

    And for anyone else, here's why you are wrong about your H in two
    sentences. The string ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the halting computation of Ĥ
    applied to ⟨Ĥ⟩. Your H rejects the string ⟨Ĥ⟩ ⟨Ĥ⟩ when it should, in
    fact, accept it.

    That is a ridiculously foolish thing to say:
    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞

    By accepting the ⟨Ĥ1⟩ ⟨Ĥ2⟩ (indicating the input does halt) the input
    never halts.

    By Jove, I think you've got it!! If I can stomach using your
    non-technical terms for once the converse also holds: By rejecting the ⟨Ĥ1⟩ ⟨Ĥ2⟩ (indicating the input does not halt) the input halts.


    The string ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the halting computation of Ĥ
    applied to ⟨Ĥ⟩. Your H rejects the string ⟨Ĥ⟩ ⟨Ĥ⟩ when it should, in
    fact, accept it.

    Which causes it to never halts thus your:

    Your H rejects the string ⟨Ĥ⟩ ⟨Ĥ⟩ when it should, in fact, accept it.
    Is very stupidly incorrect.

    The only question is in which way your Ĥ (and thus your H) is wrong, and you've told us enough times: it's wrong because it rejects ⟨Ĥ⟩ ⟨Ĥ⟩. But
    ⟨Ĥ⟩ ⟨Ĥ⟩ represents a halting computation precisely because H rejects ⟨Ĥ⟩
    ⟨Ĥ⟩.

    But thanks (seriously) for pointing out my own bad wording. You are not wrong because H should accept the string ⟨Ĥ⟩ ⟨Ĥ⟩, you are wrong because
    your H rejects it. I'll try to be more careful in future.

    When we define Ĵ to be exactly like Ĥ except that it has a UTM at Ĵ.qx instead of a simulating halt decider then we can see that Ĵ applied to ⟨Ĵ⟩ never halts. There is an infinite cycle from Ĵ.qx to Ĵ.q0.

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    H.q0 ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĥ.qn

    When we apply the original H to ⟨Ĵ⟩ ⟨Ĵ⟩ it transitions to its final state of H.qn

    Can you understand that the direct execution of Ĵ on input ⟨Ĵ⟩ is not computationally equivalent to simulating halt decider H applied to ⟨Ĵ⟩ ⟨Ĵ⟩ ?




    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Mon Aug 23 22:52:04 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/23/2021 10:09 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/23/2021 6:26 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/23/2021 2:30 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    I ignore dishonest dodges away from the point at hand.
    OK, let's do that:
    "⟨Ĥ⟩ ⟨Ĥ⟩ is not a string that encodes a halting computation" >>> is wrong. You wrote that immediately after a line showing that Ĥ
    applied to ⟨Ĥ⟩ halts. Everything since then has just been dodging this
    error.

    When we define Ĵ to be exactly like Ĥ except that it has a UTM at Ĵ.qx >>>> instead of a simulating halt decider then we can see that Ĵ applied to >>>> ⟨Ĵ⟩ never halts.
    The details are mess, but basically, yes. Detail errors (that would get >>> your paper rejected out of hand) available if you ask really nicely.

    Which details do you think are incorrect?

    A UTM is not a decider so the hat construction can't be applied to it.
    And if we make a "UTM-decider" (a TM that is a pure simulator except
    that is accepts those computations whose simulations terminate) we still can't apply the hat construction because it won't have a rejecting
    state. Thus your use of "exactly like Ĥ except..." is, at best, disingenuous. The differences must be greater than the "except..."
    clause suggests.


    My whole purpose was to simply show what happens when the simulating
    halt decide at Ĥ.qx only simulates its input.

    We can still have the same final states, except now that are unreachable
    dead code.

    There is an infinite cycle from Ĵ.qx to Ĵ.q0.
    No, but that's just because you've never written a UTM so you don't know >>> how such a TM would work. Ĵ applied to ⟨Ĵ⟩ is non-halting but there >>> will not be a cycle from Ĵ.q0 -> Ĵ.qx -> Ĵ.q0...[1]

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    Eh? You've just said that Ĵ applied to ⟨Ĵ⟩ is non-halting. Do you know
    what this notation means?
    And you have another problem which shows how shallow your thinking is.
    What is the state qn supposed to mean when J is a UTM?

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    Is it really that difficult to understand that I merely swapped Ĵ for
    Ĥ in the Ĥ template to create the Ĵ tempate?

    I understand that you think you can just say that, but I also understand
    the "template" better than you appear to.

    Presumably you
    agree with my wording and, in fact, J is a UTM that can only halt when
    simulating halting computations. So what's qn doing there? (J must
    have a qn for Ĵ to have qn.)

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    Do you know this means that you are claiming that Ĵ applied to ⟨Ĵ⟩ halts?

    I am not claiming that. I am making a single change to Ĥ that now has
    some unreachable dead code states.

    You just claimed the opposite. I think you are just typing
    symbols because they look good.

    Ĵ0.q0 copies its input ⟨Ĵ1⟩ to ⟨Ĵ2⟩ then Ĵ0.qx simulates Ĵ1 with the ⟨Ĵ2⟩ copy then
    Ĵ1.q0 copies its input ⟨Ĵ2⟩ to ⟨Ĵ3⟩ then Ĵ1.qx simulates Ĵ2 with the ⟨Ĵ3⟩ copy then
    Ĵ2.q0 copies its input ⟨Ĵ3⟩ to ⟨Ĵ4⟩ then Ĵ2.qx simulates Ĵ3 with the
    ⟨Ĵ4⟩ copy then ...

    No. Totally wrong. Your understanding of how a UTM works is
    embarrassingly shallow and I simply don't have time to explain it to
    you. In addition, you appear resistant to learning, so it would also be pointless. I can only suggest you change you attitude to learning and
    then read a book, Linz for example.

    If the Ĥ template stipulates that those actions occur then they occur
    when Ĥ has the one single modification of changing the simulating halt
    decider at Ĥ.qx to a UTM.

    H.q0 ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĥ.qn
    Typo: H.qn not Ĥ.qn.

    Yes, typo.

    When we apply the original H to ⟨Ĵ⟩ ⟨Ĵ⟩ it transitions to its final
    state of H.qn
    If you say so. I can't know because you are hiding H

    It is the Linz H.

    Since, against my repeated advice, you chose to use the same symbol for
    your actual TM as Linz does for his empty class of TMs you need to be
    more careful distinguishing them.

    Apparently most all of the textbooks call this H.

    "The original H" is not clear and
    discussion of it should be phrased hypothetically. You should talk
    about what Linz's H is specified to do, not what it does.


    Yes that makes sense.

    But since you brought up Linz's H, here's a question (get your avoidance waffle ready!). What is Linz's H specified to do when applied to your ⟨Ĥ⟩ ⟨Ĥ⟩? For clarity, let Linz's H be called L just for now. What goes
    after the ⊢* here:


    I am breaking that analysis down to its simpler components. We take the
    Linz Ĥ and change the simulating halt decider at Ĥ.qx to a UTM and
    rename this new machine Ĵ. The new machine has come dead code staes that
    are never reached.

    Now we apply the Linz H to ⟨Ĵ⟩ ⟨Ĵ⟩ and H transitions to its final state
    of H.qn indicating that Ĵ applied to ⟨Ĵ⟩ never halts.

    L.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* ?

    I really expect an answer to this. If you can't answer, be honest and
    say you can't.

    Maybe it is easier now.


    (well, you don't
    actually have a TM H we are just playing pretend here). For all I know, >>> your H gets this case wrong as well, but I am prepared to accept what
    you say about it.

    It is the Linz H: Nitwit !!!

    You should give some thought to being more respectful.

    I only call people a nitwit when they seem to being too disrespectful to
    me. Richard disrespectfully fails to distinguish between the words
    "before" and "after" so I gave up on him.

    I cannot believe that he actually fails to understand what all grade
    school kids understand, he is merely playing head games beyond my
    tolerance threshold.


    Can you understand that the direct execution of Ĵ on input ⟨Ĵ⟩ is not
    computationally equivalent to simulating halt decider H applied to ⟨Ĵ⟩
    ⟨Ĵ⟩ ?

    I am not going to answer trivial, patronising questions.

    It it a mandatory prerequisite to the next step of my proof that you
    are persistently (intentionally ?) failing to understand.

    Don't be daft. You can present your argument whether or not I answer
    your patronising questions. If you choose not to, that suits me better because there will be fewer errors to point out if you keep it to
    yourself.

    If you understand that the direct execution of Ĵ on input ⟨Ĵ⟩ is not >> computationally equivalent to simulating halt decider H applied to ⟨Ĵ⟩ ⟨Ĵ⟩

    then you should be able to understand that

    the direct execution of Ĥ on input ⟨Ĥ⟩ is not computationally
    equivalent to simulating halt decider at Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩.

    That is beyond absurd. I leave it to you spot the silly error in your reasoning (though you almost certainly won't be able to). And you will
    need to account for the fact that both


    My only "error" is that you very persistently and thus disrespectfully
    fail to bother to pay attention to my proof that this is correct.

    // 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));
    Output("Input_Halts = ", H1((u32)P, (u32)P));
    P((u32)P);
    }

    The fact that the first line of main() does produce different results
    than the second line of main conclusively proves that these two
    computations are computationally distinct different computations.

    The first line of main() decides that its input never halts. Because it
    is the only halt decider it must abort the simulation of its input or
    its input never halts.

    The second line of main() uses an exact copy H1 of H and reports that
    its input halts. It can see that another halt decider will abort its input.

    The third lines of main() halts.

    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn (via Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩)

    and

    Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

    and how that can be true of computations that are not "computationally equivalent". (You don't give the final state of the tape but it will be
    the same in both cases.) Let me be clear: the reasoning is silly (how
    you go from one assertion to the next) and the conclusion is wrong.
    This is not "failing to understand" it is "knowing more about the
    subject than you do".

    Your understanding of TM computations is woefully inadequate to discuss
    these matters. Almost everything you say contains errors, many of them
    huge errors that render your arguments null and void. Even so, nothing
    you say addresses the reason why your H is not a halt decider. Your H
    (not Linz's H) rejects a string that encodes a halting computation.
    It's as simple as that.


    TM's always leave most of their behavior to the imagination.
    The C code that I referenced is fully operational and shows every step.

    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Tue Aug 24 10:49:40 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/24/2021 9:09 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/23/2021 10:09 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/23/2021 6:26 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/23/2021 2:30 PM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    I ignore dishonest dodges away from the point at hand.
    OK, let's do that:
    "⟨Ĥ⟩ ⟨Ĥ⟩ is not a string that encodes a halting computation"
    is wrong. You wrote that immediately after a line showing that Ĥ
    applied to ⟨Ĥ⟩ halts. Everything since then has just been dodging this
    error.

    When we define Ĵ to be exactly like Ĥ except that it has a UTM at Ĵ.qx
    instead of a simulating halt decider then we can see that Ĵ applied to >>>>>> ⟨Ĵ⟩ never halts.
    The details are mess, but basically, yes. Detail errors (that would get >>>>> your paper rejected out of hand) available if you ask really nicely.

    Which details do you think are incorrect?

    A UTM is not a decider so the hat construction can't be applied to it.
    And if we make a "UTM-decider" (a TM that is a pure simulator except
    that is accepts those computations whose simulations terminate) we still >>> can't apply the hat construction because it won't have a rejecting
    state. Thus your use of "exactly like Ĥ except..." is, at best,
    disingenuous. The differences must be greater than the "except..."
    clause suggests.

    My whole purpose was to simply show what happens when the simulating
    halt decide at Ĥ.qx only simulates its input.

    I know, but you wanted to know what details you'd got wrong.


    If my plan was to swap the simulating halt decider at Ĥ.qx with a UTM
    and then rename this machine to Ĵ and I did swap swap the simulating
    halt decider at Ĥ.qx with a UTM and rename this machine to Ĵ then it is
    a God damned lie that I got anything wrong.

    We can still have the same final states, except now that are
    unreachable dead code.

    Except you show below this unreachable state being reached:


    No I do frigging not. The code is still there but the infinite cycle
    from Ĵ.qx to Ĵ.q0 prevents it from ever being reached.

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    The TM at Ĵ.qx is your "UTM-decider" with an unreachable reject state.
    Do you see why I don't think you know what you are saying?

    The you imagine what I mean to say instead of examining what I actually
    say is your mistake.

    This machine
    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn

    is transformed into this machine:
    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn // a machine stuck in infinitely nested simulation

    There is an infinite cycle from Ĵ.qx to Ĵ.q0.
    No, but that's just because you've never written a UTM so you don't know >>>>> how such a TM would work. Ĵ applied to ⟨Ĵ⟩ is non-halting but there
    will not be a cycle from Ĵ.q0 -> Ĵ.qx -> Ĵ.q0...[1]

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    Eh? You've just said that Ĵ applied to ⟨Ĵ⟩ is non-halting.

    This needs to be addressed.

    That you don't believe that there is a cycle from Ĵ.qx to Ĵ.q0 is flatly wrong. The design of Ĥ as a simulating halt decider stipulates that
    there is a cycle from Ĥ.qx to Ĥ.q0. Changing the simulating halt decider
    at Ĥ.qx to a UTM at Ĵ.qx makes this cycle infinite.

    And you have another problem which shows how shallow your thinking is. >>>>> What is the state qn supposed to mean when J is a UTM?

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qy ∞
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ halts, and

    Ĥ.q0 ⟨Ĥ1⟩ ⊢* Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ ⊢* Ĥ.qn
    if the simulated ⟨Ĥ1⟩ applied to ⟨Ĥ2⟩ does not halt

    Is it really that difficult to understand that I merely swapped Ĵ for >>>> Ĥ in the Ĥ template to create the Ĵ tempate?
    I understand that you think you can just say that, but I also understand >>> the "template" better than you appear to.

    Presumably you
    agree with my wording and, in fact, J is a UTM that can only halt when >>>>> simulating halting computations. So what's qn doing there? (J must >>>>> have a qn for Ĵ to have qn.)

    Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn

    Do you know this means that you are claiming that Ĵ applied to ⟨Ĵ⟩ >>> halts?

    I am not claiming that.

    So why did you write Ĵ.q0 ⟨Ĵ⟩ ⊢* Ĵ.qx ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĵ.qn?

    Because that <is> the Ĥ code with the single adaptation of swapping the simulating halt decider at Ĥ.qx with a UTM at Ĵ.qx.

    You wrote a
    formal description of something that is impossible (qn is unreachable if
    it exists at all) and which even if it were possible is not what Ĵ
    applied to ⟨Ĵ⟩ does? No, you wrote something daft without thinking or maybe without know what it meant.

    I wanted to make a single change to Ĥ so that I could show that the
    input to Ĥ.qx ⟨Ĥ1⟩ ⟨Ĥ2⟩ really does specify an infinite cycle that must
    be aborted by its simulating halt decider. You seemed to be having an impossibly difficult time understanding this.

    I am making a single change to Ĥ that now has some unreachable dead
    code states.

    Which state? Ĵ.qn? The one you show Ĵ.q0 ⟨Ĵ⟩ transitioning to? Yeah,
    sure.

    Ĵ0.q0 copies its input ⟨Ĵ1⟩ to ⟨Ĵ2⟩ then Ĵ0.qx simulates Ĵ1 with the ⟨Ĵ2⟩ copy then
    Ĵ1.q0 copies its input ⟨Ĵ2⟩ to ⟨Ĵ3⟩ then Ĵ1.qx simulates Ĵ2 with the ⟨Ĵ3⟩ copy then
    Ĵ2.q0 copies its input ⟨Ĵ3⟩ to ⟨Ĵ4⟩ then Ĵ2.qx simulates Ĵ3 with the
    ⟨Ĵ4⟩ copy then ...
    No. Totally wrong. Your understanding of how a UTM works is
    embarrassingly shallow and I simply don't have time to explain it to
    you. In addition, you appear resistant to learning, so it would also be >>> pointless. I can only suggest you change you attitude to learning and
    then read a book, Linz for example.

    If the Ĥ template stipulates that those actions occur then they occur
    when Ĥ has the one single modification of changing the simulating halt
    decider at Ĥ.qx to a UTM.

    No. Give this up. You don't understand what a UTM is, and I can't
    possibly teach you. You have the result you want: the "other TM
    computation" is non-halting but it does not do that in the way you
    think, but if you keep giving details, I'll have to keep replying that
    you are wrong.

    H.q0 ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* Ĥ.qn
    Typo: H.qn not Ĥ.qn.

    Yes, typo.
    ...
    It is the Linz H.

    Since, against my repeated advice, you chose to use the same symbol for
    your actual TM as Linz does for his empty class of TMs you need to be
    more careful distinguishing them.

    Apparently most all of the textbooks call this H.

    Which is further evidence that you should not. These books use H to
    refer to a hypothetical member of an empty class of TMs. Your H is
    real. It does stuff. It is not a member of an empty set. And gets at
    least one instance of the halting problem wrong because your H rejects
    the string ⟨Ĥ⟩ ⟨Ĥ⟩.


    When I refer to the Linz H it is still hypothetical because I do not
    show all of the steps.

    But since you brought up Linz's H, here's a question (get your avoidance >>> waffle ready!). What is Linz's H specified to do when applied to your
    ⟨Ĥ⟩ ⟨Ĥ⟩? For clarity, let Linz's H be called L just for now. What goes
    after the ⊢* here:


    I am breaking that analysis down to its simpler components.

    So you are not going to answer. OK, it was a lot to expect -- a direct answer to a simple question.


    Do you think that the Linz H might possibly do what Linz specified or do
    you think that maybe I mean for it to go to the store and buy some
    groceries? It is a very disingenuous question. Beside that I am freaking applying the Linz H to ⟨Ĵ⟩ ⟨Ĵ⟩, not ⟨Ĥ⟩ ⟨Ĥ⟩.

    If you want to see the result of applying a halt decider to a machine
    with its own halt decider look at:

    // 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 = ", H1((u32)P, (u32)P));
    }

    H1 is an exact copy of H and in the above configuration decides that P
    halts.

    We take the Linz Ĥ and change the simulating halt decider at Ĥ.qx to a
    UTM and rename this new machine Ĵ. The new machine has come dead code
    staes that are never reached.

    That won't help you say what Linz's H specified to do when applied to
    /your/ ⟨Ĥ⟩ ⟨Ĥ⟩. Note: to your ⟨Ĥ⟩ ⟨Ĥ⟩.


    The question is off-topic.
    I am only applying Ĥ to ⟨Ĥ⟩ or H to ⟨Ĵ⟩.

    Because of my recent empirical analysis with H1/P it would seem that H
    applied to ⟨Ĥ⟩ would transition to its final state of H.qy. Prior to
    this empirical analysis I had no way to verify what would happen.

    Now we apply the Linz H to ⟨Ĵ⟩ ⟨Ĵ⟩ and H transitions to its final >> state of H.qn indicating that Ĵ applied to ⟨Ĵ⟩ never halts.

    Which is not what I was asking about.

    I just answered that.


    L.q0 ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* ?

    I really expect an answer to this. If you can't answer, be honest and
    say you can't.

    Maybe it is easier now.

    For who? I already know the answer. I am asking you because you can't
    (or dare not) say.

    If you understand that the direct execution of Ĵ on input ⟨Ĵ⟩ is not >>>> computationally equivalent to simulating halt decider H applied to ⟨Ĵ⟩ ⟨Ĵ⟩

    then you should be able to understand that

    the direct execution of Ĥ on input ⟨Ĥ⟩ is not computationally
    equivalent to simulating halt decider at Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩.
    That is beyond absurd. I leave it to you spot the silly error in your
    reasoning (though you almost certainly won't be able to).

    My only "error" is that you very persistently and thus disrespectfully
    fail to bother to pay attention to my proof that this is correct.

    I have never seen anything remotely resembling a proof from you. And
    you reasoning above is absurd. It's absurd and it results in an
    incorrect conclusion.

    The proofs are what the H/P code actually does and why it does this.
    It is true that the input to H(P,P) would never halt unless H aborts the simulation of its input. This is easily verified by the execution trace
    of the code.

    It is true that whenever the input to a simulating halt decider would
    never halt unless this simulating halt decider aborts the simulation of
    this input that this simulating halt decider does correctly decide that
    this input never halts. You already agreed to this.

    On 5/11/2021 11:10 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    Truism:
    Every simulation that would never stop unless Halts() stops
    it at some point specifies infinite execution.

    Any algorithm that implements this truism is, of course, a halting
    decider.

    This leaves no legitimate basis for rebuttal.
    This leaves no legitimate basis for rebuttal.
    This leaves no legitimate basis for rebuttal.
    This leaves no legitimate basis for rebuttal.

    int main() { H1(P,P); }
    int main() { P(P); }

    The fact that the above pair agree also eliminates the illegitimate
    basis for rebuttal.

    <aside>
    Part of the problem is that you don't know what a proof is. I mean that

    Valid deduction on the basis of verifiably true premises <is> a proof
    anyone that does not understand this is a numbskull.

    literally. Your ancient error about entailment suggests that you think
    you can just add "stipulations" that make theorems into non-theorems.

    This is my only theorem, the rest is simply seeing what actual code
    actually does and why it does it:

    Simulating Halt Decider Theorem (Olcott 2020):
    A simulating halt decider correctly decides that any input that never
    halts unless the simulating halt decider aborts its simulation of this
    input is an input that never halts.

    It means you think you don't need to address the original argument
    because you think you can invalidate it with other "true" things. You
    may not know it, but this makes your "arguments" laughable in the eyes
    of educated readers. Some will find not paying attention to them the
    most respectful thing they can do.
    </aside>


    That your "rebuttals" merely side step key points might seem to be valid
    for ignorant gullible people not understanding the material well enough
    to see that you simply dodged the actual reasoning.

    Not only have you no proof, there is a trivial and concrete argument
    that you are wrong: ⟨Ĥ⟩ ⟨Ĥ⟩ encodes the halting computation of Ĥ applied
    to ⟨Ĥ⟩. H incorrectly reject that string.


    By this same reasoning we could say that P(P) encodes a halting
    computation yet in this case we can directly see all of the details of
    how you are proved wrong.

    Gullible ignorance people take emotionally charged rhetoric as
    equivalent to proof. They need not see any actual evidence. As long as
    someone in their reference group displays great confidence that their
    baseless accusation is correct then take this as proof that it is correct.

    Donald Trump's best approval rating ever was an election losing -3.9%
    This is such a large election losing margin that it could not have been overturned by the electoral college.

    Gullible fools that don't believe in approval ratings need to ask
    themselves if approval ratings can be manipulated then why didn't their
    people manipulate an approval rating to counter the many different
    scientific polls that were against Trump?

    I've cut the waffle about C code. The theorem, and the error we are currently discussing are about the behaviour or TMs.


    The x86 code generated from the C code can be verified to do what its
    specifies and it can also be verified that its decision basis is
    correct. Most of the details of TM proofs can at best only be imagined.
    These leaves huge gaps such that what is imagined does not correspond to
    what actually occurs.

    The C/x86 model of computation is known to be Turing equivalent on the
    basis of the RASP model for all computations that have all of the memory
    that they need. As long as an x86 function is a pure function of its
    inputs the C/x86 model of computation can be fully relied upon as a much
    higher level of abstraction of the behavior of actual Turing machines.

    And I've moved some quoted material to help with the context:

    And you will need to account for the fact that both

    Ĥ.q0 ⟨Ĥ⟩ ⊢* Ĥ.qn (via Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩)
    and
    Ĥ.qx ⟨Ĥ⟩ ⟨Ĥ⟩ ⊢* Ĥ.qn

    and how that can be true of computations that are not "computationally
    equivalent". (You don't give the final state of the tape but it will be >>> the same in both cases.)

    See? Every important question you just duck. Your claim that

    "execution of Ĥ on input ⟨Ĥ⟩ is not computationally equivalent to
    simulating halt decider at Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩"


    Ĥ applied to ⟨Ĥ⟩ is equivalent to int main() { P(P); } both halt.

    Ĥ.qx applied to ⟨Ĥ⟩ ⟨Ĥ⟩ is equivalent to H(P,P) booth abort the simulation of their inputs.

    is simply wrong based on facts you keep posting. I suspect you just
    don't know what any of this means and you are totally out of your
    depth. Mind you, you flop about on this issue. Elsewhere you only
    claim that the computations are distinct. Of course they are distinct.
    But here you talk about computational equivalence without, I suspect,
    knowing what that means for TMs.

    Your understanding of TM computations is woefully inadequate to discuss
    these matters. Almost everything you say contains errors, many of them
    huge errors that render your arguments null and void. Even so, nothing
    you say addresses the reason why your H is not a halt decider. Your H
    (not Linz's H) rejects a string that encodes a halting computation.
    It's as simple as that.

    TM's always leave most of their behavior to the imagination.

    No, you've just never written one or even understood one that someone
    else wrote.


    Show me a halting problem proof that has a simulating halt decider that
    is written in the Turing machine description language that has every
    single detail 100% fully specified such that a Turing machine
    interpreter could directly execute all of this code.

    No one ever did this because:
    (1) It never occurred to them that a simulating halt decider would work.
    (2) without direct memory addressing it would take at least hundreds of thousands of pages of code.

    The C code that I referenced is fully operational and shows every
    step.

    And that's a lie. You very carefully don't show the code or the
    critical steps. They are all hidden.

    The steps that the halt decider performs are very obviously
    self-evidently correct on the basis of the execution trace that is shown.
    It is very obvious that when P calls H with its own machine address and
    H is a simulating halt decider that this specifies infinitely nested simulation.

    Dishonest people can disingenuously disagree or simply fail to have the required prerequisite knowledge.

    It is also true that a simulating halt decider cannot possibly have any
    effect on the behavior of its input while it remains in pure simulation
    mode. Because H remains in pure simulation mode until after it makes its
    halt status decision we only need to examine that it had a correct basis
    and sued this correct basis correctly. 14 lines of the execution trace
    of P shows this.

    Dishonest people can disingenuously disagree or simply fail to have the required prerequisite knowledge.

    We can tell if a rebuttal is dishonest or the respondent simply fails to
    have the required prerequisite knowledge by the fact that their
    "rebuttal" is a mere dogmatic assertion without any supporting reasoning
    (liar) or sidesteps rather than directly addressed the key points (liar
    or ignorant).

    It's unfortunate for you that we
    can still work out that your code is wrong despite your efforts to hide
    it and to obscure its behaviour.

    I gave you an opportunity to write C code that is incontrovertibly "interesting" in that the specification is for a different undecidable problem, but your response was to post output showing that your (again hidden) code did not meet the specification. Then you declared that my "opinion" of what I wanted the code to do was wrong! It's hard to see
    how you expect these postings to be treated with respect. I, for one,
    am constantly biting my tongue.



    --
    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)
  • From olcott@21:1/5 to Ben Bacarisse on Sat Aug 28 09:36:44 2021
    XPost: comp.theory, comp.software-eng, sci.math.symbolic

    On 8/28/2021 7:15 AM, Ben Bacarisse wrote:
    olcott <NoOne@NoWhere.com> writes:

    On 8/27/2021 7:01 PM, Ben Bacarisse wrote:
    André G. Isaak <agisaak@gm.invalid> writes:

    On 2021-08-27 10:18, olcott wrote:
    On 8/27/2021 10:57 AM, André G. Isaak wrote:

    Ben never made any claims that it didn't perform some operation
    which could be construed as the functional equivalent of copying a >>>>>> string. He claimed that there was no *literal* copying involved
    except in the first instance.
    Indeed. I see in my absence there's been a flurry of "Ben is wrong"
    posts from PO. Thanks, to you and RD, for stepping in.

    So in other words he said that my high level abstraction was wrong on >>>>> the basis that it was a high level abstraction and did not delve into >>>>> the tedious details of how this high level abstraction is
    implemented.

    No, he was claiming that your high level abstraction was *misleading*
    and belied a lack of understanding of UTMs on your part.
    At the time I was actually calling out hard errors of fact, not just
    misleading abstractions. I was (dangerously) prepared to go along with
    the abstract view, as I (and others) have done for some time, because,
    whilst I agree it is potentially misleading, it's not actually wrong.
    But PO did not think he was talking about abstractions at the time I
    called him out on the mistake. He really did think that if you do the
    "hat" construction on a TM that is little more that a UTM, then it --
    the actual TM we'd call UTM^ -- has a cycle in its state graph allowing
    it to go from what he calls qx (the UTM's q0) back (via other states of
    course) to UTM^'s q0. And he thought that this loop is what wrote the
    endless literal copies. He used Linz's notation for TM configurations
    to show the strings right there on the tape next to each other, mid
    computation, with q0 being entered again and again.

    It does have literal endless copies and no one besides you has claimed
    otherwise.

    (1) Of something, yes, but of what? Not of what you claimed.


    When the TM copies a string the UTM must perform the functional
    equivalent of copying a string. It could be as simple as a literal copy
    of a string (with the additional overhead of simulation). From the
    simulated TM's perspective it is a literal copy of a string.

    (2) Are you backing down from your claim about the loop in the state
    transition graph?


    The loop in the state transition graph applies to the template as I
    explicitly showed in the execution trace:

    Ĵ copies its input ⟨Ĵ1⟩ to ⟨Ĵ2⟩ then simulates this input Ĵ1 with its
    input ⟨Ĵ2⟩
    which copies its input ⟨Ĵ2⟩ to ⟨Ĵ3⟩ then simulates this input Ĵ2 with
    its input ⟨Ĵ3⟩
    which copies its input ⟨Ĵ3⟩ to ⟨Ĵ4⟩ then simulates this input Ĵ3 with
    its input ⟨Ĵ4⟩ ...

    Ĵ copies Ĵ.qx simulates which essentially transitions to Ĵ1.q0.
    This is not the conventional notion of a state transition within the
    same machine. It is a more figurative use of the term so the gist of the behavior can be understood. I changed my paper so that it no longer
    refers to this cycle because the unconventional use of a term could be
    more difficult to understand.

    H.q0 ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* H.qy
    H.q0 ⟨Ĵ⟩ ⟨Ĵ⟩ ⊢* H.qy

    The bottom line of all of this is that H could recognize the infinitely
    nested simulation of Ĵ applied to ⟨Ĵ⟩ and correctly decide that Ĵ applied to ⟨Ĵ⟩ never halts.

    (3) You have it backwards. I only see posters agreeing with me on this
    topic.

    They are careful to use double-talk that does not directly contradict
    what you said. Since it is possible that the simulated Ĵ could perform a literal string copy (having the additional overhead of simulation) your statement that this is not what is occurring is flat out incorrect.

    Even if he now tries to suggest that he was using the notation in some
    sort of abstract way, the explicit cycle in the states gives a lie to
    that. He thought it was actual, literal, symbol by symbol copying every >>> time, exactly as the extra states added by the hat construction do it.



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