• Refuting the {Linz, Sipser and Kozen} HP Proofs (deciders within

    From Frank Kotler@21:1/5 to Terje Mathisen on Thu Dec 17 17:17:17 2020
    On 12/17/2020 06:48 AM, Terje Mathisen wrote:

    This is a _big_ problem imho, you Frank have been a lot more patient
    that I would have been, I would have at a minimum grey-listed olcott,
    i.e. only manually forwarded any messages that were clearly relevant to
    clax.

    Terje


    Sorry. I hope it is solved.

    Best,
    Frank

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to Frank Kotler on Thu Dec 17 17:19:59 2020
    On 12/17/2020 4:17 PM, Frank Kotler wrote:
    On 12/17/2020 06:48 AM, Terje Mathisen wrote:

    This is a _big_ problem imho, you Frank have been a lot more patient
    that I would have been, I would have at a minimum grey-listed olcott,
    i.e. only manually forwarded any messages that were clearly relevant
    to clax.

    Terje


    Sorry. I hope it is solved.

    Best,
    Frank



    I initially accidentally added this group to the cross-post list because
    I am unable to wear my glasses for a few weeks. I try to always post to comp.theory and two other groups.

    --
    Copyright 2020 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 James Harris@21:1/5 to Frank Kotler on Sat Dec 19 11:57:28 2020
    On 17/12/2020 06:41, Frank Kotler wrote:

    ...

    Hi Pete,

    As moderator of this newsgroup, I am very reluctant to reject your
    messages just because I'm not interested (but I'm not). Woifgang's
    message makes me think I'm not the only one...

    Could I ask you to not post on this topic here?

    Could I ask Wolfgang (and others) to simply ignore messages you don't
    like? It only takes you a second to click "next".

    There's an "issue" here. If clax86 is on the lost of newsgroups, it
    comes to my attention. If I reject it - NONE of the messages get posted!
    If it were up to me, it wouldn't work this way, but it isn't.

    Thanks for what you are doing, Frank. IIRC you are the only one who took
    up the challenge of moderating this group and what you do for us is appreciated.

    At the risk of continuing a thread that is already off the topic of x86
    asm I wonder if there's not some way the rest of us could make the job
    of the moderator easier. Maybe that's something we should discuss.


    --
    James Harris

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kerr-Mudd,John@21:1/5 to james.harris.1@nospicedham.gmail.co on Sat Dec 19 12:22:24 2020
    On Sat, 19 Dec 2020 11:57:28 GMT, James Harris <james.harris.1@nospicedham.gmail.com> wrote:

    On 17/12/2020 06:41, Frank Kotler wrote:

    ...

    Hi Pete,

    As moderator of this newsgroup, I am very reluctant to reject your
    messages just because I'm not interested (but I'm not). Woifgang's
    message makes me think I'm not the only one...

    Could I ask you to not post on this topic here?

    Could I ask Wolfgang (and others) to simply ignore messages you don't
    like? It only takes you a second to click "next".

    Sounds a sensible approach.

    There's an "issue" here. If clax86 is on the lost of newsgroups, it
    comes to my attention. If I reject it - NONE of the messages get
    posted! If it were up to me, it wouldn't work this way, but it isn't.

    Thanks for what you are doing, Frank. IIRC you are the only one who
    took up the challenge of moderating this group and what you do for us
    is appreciated.

    At the risk of continuing a thread that is already off the topic of
    x86 asm I wonder if there's not some way the rest of us could make the
    job of the moderator easier. Maybe that's something we should discuss.

    Is there any need for moderating? Just ignore any religious posts.

    --
    Bah, and indeed, Humbug.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Bernhard Schornak@21:1/5 to All on Tue Dec 22 11:07:44 2020
    olcott wrote:

    _H_Hat:
    [000005e6](01) 55 push ebp
    [000005e7](02) 8bec mov ebp,esp
    [000005e9](01) 51 push ecx
    [000005ea](03) 8b4508 mov eax,[ebp+08]
    [000005ed](01) 50 push eax
    [000005ee](03) 8b4d08 mov ecx,[ebp+08]
    [000005f1](01) 51 push ecx
    [000005f2](05) e8effdffff call 000003e6
    [000005f7](03) 83c408 add esp,+08
    [000005fa](03) 8945fc mov [ebp-04],eax
    [000005fd](04) 837dfc00 cmp dword [ebp-04],+00
    [00000601](02) 7404 jz 00000607
    [00000603](02) ebfe jmp 00000603
    [00000605](02) eb01 jmp 00000608
    [00000607](01) f4 hlt
    [00000608](02) 8be5 mov esp,ebp
    [0000060a](01) 5d pop ebp
    [0000060b](01) c3 ret


    0603 jumps to itself. Reduce to

    _H-Hat:movl 0x0C(%esp), %eax
    subl $0x08, %esp
    movl %eax, 0x00(%esp)
    movl %eax, 0x04(%esp)
    call _WHATEVER_THAT_IS
    testl %eax, %eax
    je 0f
    L00:jmp L00 # loop forever
    0:hlt # CLI/STI?
    addl $0x08, %esp
    ret



    As long as the code at 0x03E6 is unknown, it is impossible to tell
    anything. _H_Hat itself does nothing ... except wasting clocks and
    electrical power when the returned value is not zero.

    The only thing I can see in your debug trace is that you would run
    out of stack, if the debugger did not stop your attempts with this
    error message before ESP reached your stack's bottom. Maybe a good
    proof the debugger works well, but nothing else... ;)


    Merry Winter Solstice!

    Bernhard Schornak

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to Bernhard Schornak on Tue Dec 22 09:55:19 2020
    XPost: comp.theory

    On 12/22/2020 4:07 AM, Bernhard Schornak wrote:
    olcott wrote:

    _H_Hat:
    [000005e6](01)  55                  push ebp [000005e7](02)  8bec                mov ebp,esp [000005e9](01)  51                  push ecx [000005ea](03)  8b4508              mov eax,[ebp+08] [000005ed](01)  50                  push eax [000005ee](03)  8b4d08              mov ecx,[ebp+08] [000005f1](01)  51                  push ecx [000005f2](05)  e8effdffff          call 000003e6
    [000005f7](03)  83c408              add esp,+08 [000005fa](03)  8945fc              mov [ebp-04],eax [000005fd](04)  837dfc00            cmp dword [ebp-04],+00 [00000601](02)  7404                jz 00000607 [00000603](02)  ebfe                jmp 00000603 [00000605](02)  eb01                jmp 00000608 [00000607](01)  f4                  hlt
    [00000608](02)  8be5                mov esp,ebp [0000060a](01)  5d                  pop ebp [0000060b](01)  c3                  ret


    0603 jumps to itself. Reduce to

    _H-Hat:movl  0x0C(%esp), %eax
           subl  $0x08,      %esp
           movl  %eax,       0x00(%esp)
           movl  %eax,       0x04(%esp)
           call  _WHATEVER_THAT_IS
           testl %eax,       %eax
           je    0f
       L00:jmp   L00                      # loop forever
         0:hlt                            # CLI/STI?
           addl $0x08,       %esp
           ret



    As long as the code at 0x03E6 is unknown, it is impossible to tell
    anything. _H_Hat itself does nothing ... except wasting clocks and
    electrical power when the returned value is not zero.

    The only thing I can see in your debug trace is that you would run
    out of stack,

    That is the answer that I expected and confirms that I am correct.

    I am using the x86 code that was translated from C as the machine
    description language of a Universal Turing Machine equivalent. I wrote a
    whole x86utm operating system for this purpose. This means that the
    assumption is infinite memory and thus infinite stack.

    if the debugger did not stop your attempts with this
    error message before ESP reached your stack's bottom. Maybe a good
    proof the debugger works well, but nothing else... ;)


    In my actual test case the debugger is a halt decider that recognizes
    the pattern, (in my prior post) stops simulating this code and reports
    not halting.

    It turns out that all the halting problem proofs depend on the
    assumption that such a halt decider is impossible.

    Thanks for your help. The people in the other forums don't seem to have
    a clue about the x86 language.


    Merry Winter Solstice!

    Bernhard Schornak



    --
    Copyright 2020 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 Robert@21:1/5 to NoOne@nospicedham.nowhere.com on Tue Dec 22 17:40:39 2020
    XPost: comp.theory

    In comp.lang.asm.x86 olcott <NoOne@nospicedham.nowhere.com> wrote in part:
    On 12/22/2020 4:07 AM, Bernhard Schornak wrote:
    olcott wrote:

    _H_Hat:
    [000005e6](01)? 55????????????????? push ebp
    [000005e7](02)? 8bec??????????????? mov ebp,esp
    [000005e9](01)? 51????????????????? push ecx
    [000005ea](03)? 8b4508????????????? mov eax,[ebp+08]
    [000005ed](01)? 50????????????????? push eax
    [000005ee](03)? 8b4d08????????????? mov ecx,[ebp+08]
    [000005f1](01)? 51????????????????? push ecx
    [000005f2](05)? e8effdffff????????? call 000003e6
    [000005f7](03)? 83c408????????????? add esp,+08
    [000005fa](03)? 8945fc????????????? mov [ebp-04],eax
    [000005fd](04)? 837dfc00??????????? cmp dword [ebp-04],+00
    [00000601](02)? 7404??????????????? jz 00000607
    [00000603](02)? ebfe??????????????? jmp 00000603
    [00000605](02)? eb01??????????????? jmp 00000608
    [00000607](01)? f4????????????????? hlt
    [00000608](02)? 8be5??????????????? mov esp,ebp
    [0000060a](01)? 5d????????????????? pop ebp
    [0000060b](01)? c3????????????????? ret


    0603 jumps to itself. Reduce to

    _H-Hat:movl? 0x0C(%esp), %eax
    ?????? subl? $0x08,????? %esp
    ?????? movl? %eax,?????? 0x00(%esp)
    ?????? movl? %eax,?????? 0x04(%esp)
    ?????? call? _WHATEVER_THAT_IS
    ?????? testl %eax,?????? %eax
    ?????? je??? 0f
    ?? L00:jmp?? L00????????????????????? # loop forever
    ???? 0:hlt??????????????????????????? # CLI/STI?
    ?????? addl $0x08,?????? %esp
    ?????? ret



    As long as the code at 0x03E6 is unknown, it is impossible to tell
    anything. _H_Hat itself does nothing ... except wasting clocks and
    electrical power when the returned value is not zero.

    The only thing I can see in your debug trace is that you would run
    out of stack,

    If it doesn't get caught in the infinite loop at 603, likely less
    than one million before you hit the stack guard page.


    That is the answer that I expected and confirms that I am correct.

    I am using the x86 code that was translated from C as the
    machine description language of a Universal Turing Machine
    equivalent. I wrote a whole x86utm operating system for
    this purpose. This means that the assumption is infinite
    memory and thus infinite stack.

    ??? I don't think any general-use compiler will emit a HLT
    instruction. No need, this is a priviliged ring0 instruction
    on modern x86 p-mode OSes.

    -- Robert

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From olcott@21:1/5 to Robert on Tue Dec 22 16:19:10 2020
    XPost: comp.theory

    On 12/22/2020 11:40 AM, Robert wrote:
    In comp.lang.asm.x86 olcott <NoOne@nospicedham.nowhere.com> wrote in part:
    On 12/22/2020 4:07 AM, Bernhard Schornak wrote:
    olcott wrote:

    _H_Hat:
    [000005e6](01)? 55????????????????? push ebp
    [000005e7](02)? 8bec??????????????? mov ebp,esp
    [000005e9](01)? 51????????????????? push ecx
    [000005ea](03)? 8b4508????????????? mov eax,[ebp+08]
    [000005ed](01)? 50????????????????? push eax
    [000005ee](03)? 8b4d08????????????? mov ecx,[ebp+08]
    [000005f1](01)? 51????????????????? push ecx
    [000005f2](05)? e8effdffff????????? call 000003e6
    [000005f7](03)? 83c408????????????? add esp,+08
    [000005fa](03)? 8945fc????????????? mov [ebp-04],eax
    [000005fd](04)? 837dfc00??????????? cmp dword [ebp-04],+00
    [00000601](02)? 7404??????????????? jz 00000607
    [00000603](02)? ebfe??????????????? jmp 00000603
    [00000605](02)? eb01??????????????? jmp 00000608
    [00000607](01)? f4????????????????? hlt
    [00000608](02)? 8be5??????????????? mov esp,ebp
    [0000060a](01)? 5d????????????????? pop ebp
    [0000060b](01)? c3????????????????? ret


    0603 jumps to itself. Reduce to

    _H-Hat:movl? 0x0C(%esp), %eax
    ?????? subl? $0x08,????? %esp
    ?????? movl? %eax,?????? 0x00(%esp)
    ?????? movl? %eax,?????? 0x04(%esp)
    ?????? call? _WHATEVER_THAT_IS
    ?????? testl %eax,?????? %eax
    ?????? je??? 0f
    ?? L00:jmp?? L00????????????????????? # loop forever
    ???? 0:hlt??????????????????????????? # CLI/STI?
    ?????? addl $0x08,?????? %esp
    ?????? ret



    As long as the code at 0x03E6 is unknown, it is impossible to tell
    anything. _H_Hat itself does nothing ... except wasting clocks and
    electrical power when the returned value is not zero.

    The only thing I can see in your debug trace is that you would run
    out of stack,

    If it doesn't get caught in the infinite loop at 603, likely less
    than one million before you hit the stack guard page.


    It is only this portion of the excution trace of H_Hat that I am
    referring to. The second call 000003e6 from the same machine address
    [000005f2] without any control flow instructions inbetween indicates
    infinite recursion. Many of the comp.theory people could not understand
    this.

    ---[000005e6](01) 55 push ebp
    ---[000005e7](02) 8bec mov ebp,esp
    ---[000005e9](01) 51 push ecx
    ---[000005ea](03) 8b4508 mov eax,[ebp+08]
    ---[000005ed](01) 50 push eax
    ---[000005ee](03) 8b4d08 mov ecx,[ebp+08]
    ---[000005f1](01) 51 push ecx
    ---[000005f2](05) e8effdffff call 000003e6 --CALL [000003e6] ---[000005e6](01) 55 push ebp
    ---[000005e7](02) 8bec mov ebp,esp
    ---[000005e9](01) 51 push ecx
    ---[000005ea](03) 8b4508 mov eax,[ebp+08]
    ---[000005ed](01) 50 push eax
    ---[000005ee](03) 8b4d08 mov ecx,[ebp+08]
    ---[000005f1](01) 51 push ecx
    ---[000005f2](05) e8effdffff call 000003e6 --CALL
    [000003e6]

    That is the answer that I expected and confirms that I am correct.

    I am using the x86 code that was translated from C as the
    machine description language of a Universal Turing Machine
    equivalent. I wrote a whole x86utm operating system for
    this purpose. This means that the assumption is infinite
    memory and thus infinite stack.

    ??? I don't think any general-use compiler will emit a HLT
    instruction. No need, this is a priviliged ring0 instruction
    on modern x86 p-mode OSes.

    -- Robert


    I use it in the x86 emulator to indicate the that system definitely
    stopped executing at this point. Before I used this instruction the
    emulator tended to try to execute garbage. When it popped the return
    from main() it had no where to go.

    --
    Copyright 2020 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 Bernhard Schornak@21:1/5 to olcott on Wed Dec 23 04:33:01 2020
    olcott wrote:


    I use it in the x86 emulator to indicate the that system definitely stopped executing at this point.
    Before I used this instruction the emulator tended to try to execute garbage. When it popped the
    return from main() it had no where to go.


    This is circular reasoning, because your thought depends on
    the unproven assumption your x86 emulator throws the proper
    results under any circumstance. Does it work with any other
    emulator, as well?


    Greetings from Augsburg

    Bernhard Schornak

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