Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.software-eng > #1932 > unrolled thread

Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )

Started byolcott <NoOne@NoWhere.com>
First post2020-11-27 11:10 -0600
Last post2020-11-27 17:09 -0600
Articles 13 on this page of 33 — 3 participants

Back to article view | Back to comp.software-eng

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 11:10 -0600
    Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-27 17:24 +0000
      Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 11:54 -0600
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 13:34 -0600
          Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 14:04 -0600
          Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:24 -0600
          Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-27 21:57 -0600
            Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-30 11:55 -0600
              Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 21:06 +0000
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 15:14 -0600
                  Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-11-30 22:48 +0000
                    Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 17:23 -0600
                      Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-30 23:54 +0000
                        Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:08 -0600
                        Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:18 -0600
                          Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 18:59 -0600
                          Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 01:40 +0000
                            Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 19:48 -0600
                              Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 08:41 +0000
                                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 08:52 -0600
                                  Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 21:30 +0000
                                    Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 16:34 -0600
                                      Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 23:10 +0000
                                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 12:12 -0600
                                  Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 18:35 +0000
                                    Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 12:54 -0600
                            Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 10:08 -0600
                      Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Kaz Kylheku <563-365-8930@kylheku.com> - 2020-12-01 01:23 +0000
                        Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-11-30 19:30 -0600
    Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 12:46 -0600
      Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:40 -0600
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 15:52 -0600
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) olcott <NoOne@NoWhere.com> - 2020-11-27 17:09 -0600

Page 2 of 2 — ← Prev page 1 [2]


#2020 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 21:30 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201201132248.326@kylheku.com>
In reply to#2012
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
> This is computationally equivalent to every conventional halting problem 
> counter-example that "does the opposite of whatever the halt decide 
> decides":
>
> void H_Hat(u32 P)
> {
>    u32 Input_Halts = Halts(P, P);
>    if (!Input_Halts)
>      HALT
>    else
>      HERE: goto HERE;
> }

This is just an element of the "educational" version of the proof.

It's obvious to everyone that strawman interpretations of this have
weaknesses; if it were compiled on an actual machine, there will be
instruction sequences that a VM could look for to detect the trivial
loop and such.

You must make the strongest possible interpretation of this.
For instance, H_Hat can invoke Halts using a tamper-proof virtual
machine of its own.

Or: I can write H_Hat in a custom programming language, which compiles
to byte code. And then H_Hat looks like this:


   uint8_t H_Hat_Bytecode = { 0xF3, 0xD9, ... reams of hex };

   void H_Hat(P)
   {
      H_Hat_Bytecode_Execute(H_Hat_Bytecode, P);
   }

now the "HERE: goto HERE" is hidden in bytecode. A completely different
strategy is needed to discover it, since it is not apparent in any
native instruction sequence.

-- 
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

[toc] | [prev] | [next] | [standalone]


#2024 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 16:34 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<ULGdnUkRI-FpWVvCnZ2dnUU7-X3NnZ2d@giganews.com>
In reply to#2020
On 12/1/2020 4:22 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> On 12/1/2020 3:30 PM, Kaz Kylheku wrote:
>>> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>>>> On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
>>>> This is computationally equivalent to every conventional halting problem
>>>> counter-example that "does the opposite of whatever the halt decide
>>>> decides":
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>>      u32 Input_Halts = Halts(P, P);
>>>>      if (!Input_Halts)
>>>>        HALT
>>>>      else
>>>>        HERE: goto HERE;
>>>> }
>>>
>>> This is just an element of the "educational" version of the proof.
>>>
>>> It's obvious to everyone that strawman interpretations of this have
>>> weaknesses; if it were compiled on an actual machine, there will be
>>> instruction sequences that a VM could look for to detect the trivial
>>> loop and such.
>>>
>>> You must make the strongest possible interpretation of this.
>>> For instance, H_Hat can invoke Halts using a tamper-proof virtual
>>> machine of its own.
>>
>> I only have to find one case of the conventional halting problem proof
>> "do the opposite of whatever the halt decider decides" to refute all of
>> these proofs.
> 
> You're only refuting a strawman interpretation of proof sketches.
> 
> Those proof skeches are for educational purposes; they are not the
> intellectual work that underlies our understanding of computability.
> 
>>> Or: I can write H_Hat in a custom programming language, which compiles
>>> to byte code. And then H_Hat looks like this:
>>>
>>>
>>>      uint8_t H_Hat_Bytecode = { 0xF3, 0xD9, ... reams of hex };
>>>
>>>      void H_Hat(P)
>>>      {
>>>         H_Hat_Bytecode_Execute(H_Hat_Bytecode, P);
>>>      }
> 
> The above is still the "conventional template"; I just compiled
> it a particular way.
> 
> That is to say, I can have a program which /automatically/ converts this:
> 
>       void H_Hat(P)
>       {
>          if (Halts(P, P))
>          {
>              for (;;);
>          }
>          else
>          {
>              HALT;
>          }
>       }
> 
> into custom byte code:
> 
>      void H_Hat(P)
>      {
>         static uint8_t bytecode = { 0xF3, 0xD9, ... };
>         bytecode_execute(bytecode, P);
>      }
> 
> I'm still conforming to the template.

You don't seem to be able to understand this:
Any example where the template is decidable is all that is needed to 
prove that the template itself does not prove undecidability.

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#2025 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 23:10 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201201150342.507@kylheku.com>
In reply to#2024
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> You don't seem to be able to understand this:
> Any example where the template is decidable is all that is needed to 
> prove that the template itself does not prove undecidability.

Yes; the template itself doesn't do any such thing. It's only an
illustration of the method, which you are supposed to apply in the best
possible way in order to break a given proposed halting decider.

The main idea is that for any function offered as a halting decider,
we can use the method to find a breaking example.

Similarly to how "the map is not the territory", the template is not the
method.

-- 
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

[toc] | [prev] | [next] | [standalone]


#2016 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 12:12 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<lvSdnVrkbdISGlvCnZ2dnUU7-fvNnZ2d@giganews.com>
In reply to#2011
On 12/1/2020 11:32 AM, Kaz Kylheku wrote:
> On 2020-12-01, Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>> On Tuesday, 1 December 2020 at 08:42:01 UTC, Kaz Kylheku wrote:
>>> On 2020-12-01, olcott <No...@NoWhere.com> wrote:
>>>> I skimmed what you said below and it is all beside the point that I just
>>>> made.
>>> Here we go: this is how you dismiss situations that reveal flaws in your
>>> so-called work, and then continue to claim that no flaws have been found.
>>>> The H_Hat template <is> the template of every conventional halting
>>>> problem proof, thus deciding this one template refutes all these proofs.
>>> In other words, you're attacking a strawman version of the proof,
>>> by taking a particular pseudo-code template literally.
>>>
>>> You're not taking on the general technique given in the proof.
>>>
>> No, that's reasonable. If he can produc a pair of Turing machines,
>> one of which is a "partial halt decider", the other which calls that
>> decider and inverts the result, and somehow gets consistent results
>> on the call to the decider and the direct run, then he's refuted the proof.
> 
> Olcott is working against strawman versions of the proof which use
> hand-waving arguments and pseudo-code in order to be easy to follow.
> 
Like I said I am stopping after correcting your first mistake.

Actual debug trace of Halts() deciding halting on H_Hat()

I spent about 3000 hours creating the x86utm operating system that 
executes x86 based virtual machines using a very excellent x86 emulator. 
It executes the COFF object file output of the Microsoft C compiler 
using x86 emulation.

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine
It is common knowledge that all x86 based programs are computationally 
equivalent to UTMs for every computation that does not require more 
memory than they have.

The following is fully executable code and its complete execution trace 
is provided below.

void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}


int main()
{
   DebugTrace((u32)H_Hat, (u32)H_Hat);
   HALT;
}


_H_Hat()
[00000584](01)  55                  push ebp
[00000585](02)  8bec                mov ebp,esp
[00000587](01)  51                  push ecx
[00000588](03)  8b4508              mov eax,[ebp+08]
[0000058b](01)  50                  push eax
[0000058c](03)  8b4d08              mov ecx,[ebp+08]
[0000058f](01)  51                  push ecx
[00000590](05)  e8bffdffff          call 00000354
[00000595](03)  83c408              add esp,+08
[00000598](03)  8945fc              mov [ebp-04],eax
[0000059b](04)  837dfc00            cmp dword [ebp-04],+00
[0000059f](02)  7403                jz 000005a4
[000005a1](01)  f4                  hlt
[000005a2](02)  eb02                jmp 000005a6
[000005a4](02)  ebfe                jmp 000005a4
[000005a6](02)  8be5                mov esp,ebp
[000005a8](01)  5d                  pop ebp
[000005a9](01)  c3                  ret

_main()
[000005b4](01)  55                  push ebp
[000005b5](02)  8bec                mov ebp,esp
[000005b7](05)  6884050000          push 00000584
[000005bc](05)  6884050000          push 00000584
[000005c1](05)  e88efdffff          call 00000354
[000005c6](03)  83c408              add esp,+08
[000005c9](01)  f4                  hlt
[000005ca](01)  5d                  pop ebp
[000005cb](01)  c3                  ret


Output_Debug_Trace() [00010bd3]  size(80)  capacity(65536)
[000005b4](01)  55                  push ebp
[000005b5](02)  8bec                mov ebp,esp
[000005b7](05)  6884050000          push 00000584
[000005bc](05)  6884050000          push 00000584
[000005c1](05)  e88efdffff          call 00000354   	----CALL [00000354]
[00000584](01)  55                  push ebp
[00000585](02)  8bec                mov ebp,esp
[00000587](01)  51                  push ecx
[00000588](03)  8b4508              mov eax,[ebp+08]
[0000058b](01)  50                  push eax
[0000058c](03)  8b4d08              mov ecx,[ebp+08]
[0000058f](01)  51                  push ecx
[00000590](05)  e8bffdffff          call 00000354   	----CALL [00000354]
[00000584](01)  55                  push ebp
[00000585](02)  8bec                mov ebp,esp
[00000587](01)  51                  push ecx
[00000588](03)  8b4508              mov eax,[ebp+08]
[0000058b](01)  50                  push eax
[0000058c](03)  8b4d08              mov ecx,[ebp+08]
[0000058f](01)  51                  push ecx
[00000590](05)  e8bffdffff          call 00000354   	----CALL [00000354]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#2017 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 18:35 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201201101804.411@kylheku.com>
In reply to#2016
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> The following is fully executable code and its complete execution trace 
> is provided below.
>
> void H_Hat(u32 P)
> {
>    u32 Aborted = DebugTrace(P, P);
>    if (Aborted)
>      HALT
>    else
>      HERE: goto HERE;
> }
>
>
> int main()
> {
>    DebugTrace((u32)H_Hat, (u32)H_Hat);
>    HALT;
> }

[ snip ]

> [00000590](05)  e8bffdffff          call 00000354   	----CALL [00000354]

> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

OK, so here, we are inside H_Hat and invoked DebugTrace(P, P), right?
This DebugTrace machine has detected a trivial recursion, right? And so,
in that case, it terminates with the above diagnostic message and
returns a nonzero value.

So now, we have a non-zero Aborted value from DebugTrace(P, P).
Thus, the if statement calls HALT.

Well, what does that mean? Presumably, the outer DebugTrace in main
will now terminate. (With a zero, since it was due to a HALT and not
a simulator-induced abort.)

Thus, now control pops out of the DebugTrace call in main, and
falls through to main's HALT; and that's that.

I don't understand what is the decision verdict. The program has
stopped, surely enough, but what has the program decided?

- Has it decided that H_Hat(H_Hat) halts?

- Or has it decided that it does not halt?

Since H_Hat(H_Hat) hit infinite recursion, it should somehow be reporting
"does not halt", right?

Consider the following two programs, based on the above program. All I
have done is changed H_Hat. Do these two programs report different
decisions from each other? How do they do that?

  void H_Hat(u32 P)
  {
    HALT;
  }

  int main()
  {
     DebugTrace((u32)H_Hat, (u32)H_Hat);
     HALT;
  }

and:

  void H_Hat(u32 P)
  {
    HERE: goto HERE;
  }

  int main()
  {
     DebugTrace((u32)H_Hat, (u32)H_Hat);
     HALT;
  }

(Related question: will the DebugTrace halt in this second program?
Does DebugTrace detect a trivial "HERE: goto here;" loop, like it
detects recursion?)


-- 
TXR Programming Language: http://nongnu.org/txr
Music DIY Mailing List:  http://www.kylheku.com/diy
ADA MP-1 Mailing List:   http://www.kylheku.com/mp1

[toc] | [prev] | [next] | [standalone]


#2018 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 12:54 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<4eednaTjve7hDFvCnZ2dnUU7-IGdnZ2d@giganews.com>
In reply to#2017
On 12/1/2020 12:35 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> The following is fully executable code and its complete execution trace
>> is provided below.
>>
>> void H_Hat(u32 P)
>> {
>>     u32 Aborted = DebugTrace(P, P);
>>     if (Aborted)
>>       HALT
>>     else
>>       HERE: goto HERE;
>> }
>>
>>
>> int main()
>> {
>>     DebugTrace((u32)H_Hat, (u32)H_Hat);
>>     HALT;
>> }
> 
> [ snip ]
> 
>> [00000590](05)  e8bffdffff          call 00000354   	----CALL [00000354]
> 
>> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:
> 
> OK, so here, we are inside H_Hat and invoked DebugTrace(P, P), right?
> This DebugTrace machine has detected a trivial recursion, right? And so,
> in that case, it terminates with the above diagnostic message and
> returns a nonzero value.

Any time the same function is called from the same machine address 
without any conditional branch instructions in-between we have infinite 
recursion.

> So now, we have a non-zero Aborted value from DebugTrace(P, P).
> Thus, the if statement calls HALT.

No, it is the call to DebugTrace() is aborted before ever returning any 
value to H_Hat.

> Well, what does that mean? Presumably, the outer DebugTrace in main
> will now terminate. (With a zero, since it was due to a HALT and not
> a simulator-induced abort.)
> 

No the operating system is the halt decider as exaplained in my other 
reply.

> Thus, now control pops out of the DebugTrace call in main, and
> falls through to main's HALT; and that's that.

No main() is aborted by the operating system before then.

> I don't understand what is the decision verdict. The program has
> stopped, surely enough, but what has the program decided?
> 

 >> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

The entire simulation of all user code is stopped as soon as some of the 
user code was found to be infinitely recursive.


The operating system version of Halts is invoked against main() as 
required by these two cases:


int main()
{
HERE: goto HERE;
   OutputString("Hello World!");
   HALT;
}


int main()
{
   H_Hat((u32)H_Hat);
   HALT;
}

> - Has it decided that H_Hat(H_Hat) halts?
> 
> - Or has it decided that it does not halt?
> 
> Since H_Hat(H_Hat) hit infinite recursion, it should somehow be reporting
> "does not halt", right?
> 
> Consider the following two programs, based on the above program. All I
> have done is changed H_Hat. Do these two programs report different
> decisions from each other? How do they do that?
> 
>    void H_Hat(u32 P)
>    {
>      HALT;
>    }
> 
>    int main()
>    {
>       DebugTrace((u32)H_Hat, (u32)H_Hat);
>       HALT;
>    }
> 
> and:
> 
>    void H_Hat(u32 P)
>    {
>      HERE: goto HERE;
>    }
> 
>    int main()
>    {
>       DebugTrace((u32)H_Hat, (u32)H_Hat);
>       HALT;
>    }
> 
> (Related question: will the DebugTrace halt in this second program?
> Does DebugTrace detect a trivial "HERE: goto here;" loop, like it
> detects recursion?)
> 
> 


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#2014 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 10:08 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<AvWdna1EjI3491vCnZ2dnUU7-WHNnZ2d@giganews.com>
In reply to#2004
On 11/30/2020 7:40 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> int DebugTrace(u32 P, u32 I)
>> {
>>     ((int(*)(int))P)(I);
>>     return 1;
>> }
>>
>> void H_Hat(u32 P)
>> {
>>     u32 Aborted = DebugTrace(P, P);
>>     if (Aborted)
>>       HALT
>>     else
>>       HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>     u32 P = (u32)H_Hat;
>>     DebugTrace(P, P);
>>     HALT;
>> }
>>
>>   From the above infinite recursion it is easy to see that when
>> DebugTrace(P, P) is replaced with a full x86 emulator that we still have
>> infinite recursion.
> 
> In that case we must detect the recursion and report that the program
> does not halt; we can't just let it go on. This means that we are
> looking for a specific pattern of execution which looks like runaway
> recursion.
> 
> Problem is, H_Hat can be this (among other possible structures in a
> similar vain):
> 
>   void H_Hat(u32 P)
>   {
>      Decoy_1003(P); // One of an infinite library of decoys
> 
>      u32 Aborted = DebugTrace(P, P);
>      if (Aborted)
>        HALT
>      else
>        HERE: goto HERE;
>   }
> 
> Some of the decoys terminate, and so the DebugTrace line is
> executed. Some do not terminate.
> 
> The manners in which the non-terminating ones fail to terminate is
> completely arbitrary; it doesn't necessarily look anything like the
> infinite recursion execution trace pattern.
> 
> Stepping through a program to decide its halting is completely
> wrongheaded. We cannot decide halting that way. If we actually
> execute a program P on input I, it either halts (whereupon halting
> is decided) or does not, in which case halting remains undecided.
> 
> To decide halting means to calculate, in a finite number of steps,
> whether any P on any I halts or does not halt.
> 
> Allowing P to execute, and monitoring it for specific non-termination
> patterns does not add up to a halting decider.
> 
> The problem is that as you execute P(I), looking for it to hit
> one of the specific non-terminating patterns, it might appear not
> to be hitting any of those patterns---and yet not terminating!
> 
> Your only choices are:
> 
> 1) step yet anoher instruction cycle and hope that one of the
> non-termination patterns (such as a specific instance of runaway
> recursion) appears, so you can conclude "does not terminate".
> 

The only way that you can maintain your false believe that I am 
incorrect is to make sure to not pay attention to the following complete 
execution trace of fully operational code.

void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}


int main()
{
   DebugTrace((u32)H_Hat, (u32)H_Hat);
   HALT;
}


_H_Hat()
[00000584](01)  55                  push ebp
[00000585](02)  8bec                mov ebp,esp
[00000587](01)  51                  push ecx
[00000588](03)  8b4508              mov eax,[ebp+08]
[0000058b](01)  50                  push eax
[0000058c](03)  8b4d08              mov ecx,[ebp+08]
[0000058f](01)  51                  push ecx
[00000590](05)  e8bffdffff          call 00000354
[00000595](03)  83c408              add esp,+08
[00000598](03)  8945fc              mov [ebp-04],eax
[0000059b](04)  837dfc00            cmp dword [ebp-04],+00
[0000059f](02)  7403                jz 000005a4
[000005a1](01)  f4                  hlt
[000005a2](02)  eb02                jmp 000005a6
[000005a4](02)  ebfe                jmp 000005a4
[000005a6](02)  8be5                mov esp,ebp
[000005a8](01)  5d                  pop ebp
[000005a9](01)  c3                  ret

_main()
[000005b4](01)  55                  push ebp
[000005b5](02)  8bec                mov ebp,esp
[000005b7](05)  6884050000          push 00000584
[000005bc](05)  6884050000          push 00000584
[000005c1](05)  e88efdffff          call 00000354
[000005c6](03)  83c408              add esp,+08
[000005c9](01)  f4                  hlt
[000005ca](01)  5d                  pop ebp
[000005cb](01)  c3                  ret


Output_Debug_Trace() [00010bd3]  size(80)  capacity(65536)
[000005b4](01)  55                  push ebp
[000005b5](02)  8bec                mov ebp,esp
[000005b7](05)  6884050000          push 00000584
[000005bc](05)  6884050000          push 00000584
[000005c1](05)  e88efdffff          call 00000354       ----CALL [00000354]
[00000584](01)  55                  push ebp
[00000585](02)  8bec                mov ebp,esp
[00000587](01)  51                  push ecx
[00000588](03)  8b4508              mov eax,[ebp+08]
[0000058b](01)  50                  push eax
[0000058c](03)  8b4d08              mov ecx,[ebp+08]
[0000058f](01)  51                  push ecx
[00000590](05)  e8bffdffff          call 00000354       ----CALL [00000354]
[00000584](01)  55                  push ebp
[00000585](02)  8bec                mov ebp,esp
[00000587](01)  51                  push ecx
[00000588](03)  8b4508              mov eax,[ebp+08]
[0000058b](01)  50                  push eax
[0000058c](03)  8b4d08              mov ecx,[ebp+08]
[0000058f](01)  51                  push ecx
[00000590](05)  e8bffdffff          call 00000354       ----CALL [00000354]
The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#2002 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 01:23 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201130165528.727@kylheku.com>
In reply to#1997
On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
> On 11/30/2020 4:48 PM, Kaz Kylheku wrote:
>> ["Followup-To:" header set to comp.theory.]
>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>>> You still haven't explained how your non-halting decider can decide if
>>>>>> an arbitrary program given arbitrary input halts.
>>>>>
>>>>> My goal is not to actually solve the halting problem because to do this
>>>>> I would have to write a computer program that is ALL-KNOWING.
>>>>
>>>> An imaginary "all knowing" entity is called an "oracle".
>>>>
>>>> You believe that calculating halting requires an "oracle" program;
>>>> yet you don't see that as an impediment against computability?
>>>>
>>>
>>> I already posted the complete execution trace of the details of how
>>> Halts decides halting on H_Hat()
>>>
>>> void H_Hat(u32 P)
>>> {
>>>     u32 Input_Halts = Halts(P, P);
>>>     if (!Input_Halts)
>>>       HALT
>>>     else
>>>       HERE: goto HERE;
>>> }
>>>
>>> When Halts() always simulates its input it is obvious that
>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
>>> decided as non halting.
>> 
>> You're blind to the obvious issue that H_Hat isn't a single
>> function/program. It's a *class* of programs.
>> 
>
> Every element of this class (where Halts() bases its decision on 
> simulating its input) specifies infinite recursion.

Firstly, you don't yet understand what it means to decide halting.

You cannot "decide" whether a program P halts on input I simply
by running P(I).  This is because P(I) might not terminate.
Whenever P(I) does not terminate, the halting is not decided.

To decide halting means, /in a finite number of steps/ to decide whether
any P halts on any I.

You're missing he possibility that H_Hat above can include arbitrary
decoy code. For instance, like this, or in any number of other ways:

void H_Hat(u32 P)
{
    Decoy_Calculation(P); // may or may not terminate

    u32 Input_Halts = Halts(P, P);
    if (!Input_Halts)
      HALT
    else
      HERE: goto HERE;
}

If you execute this with a stepwise simulation, you will end up inside
the decoy. So then, you must decide whether that decoy terminates.
Well, assuming you even know you're inside a decoy. A decoy can look
like any innocent program. (Deciding whether the decoy part terminates:
note how that is an embedded instance of the halting problem!)

Now these programs can be generated such that sometimes the decoy does
not terminate, and sometimes it does. Whenever it doesn't terminate, the
runaway recursion part that Halt() is naively looking for is never
reached.

>> You're also forgeting that the Halts has to be *correct* on all inputs.
>> The author of Halts cannot be so obsessed with defeating H_Hat programs
>> that he overlooks correctness.
>
> So then if I correctly refute all the conventional proofs this does not 
> count until I actually solve the halting problem?

If someone were to refute the conventional proofs, it would count for
something. Namely, it would mean that computability reverts to being an
open problem. I.e. that halting may or may not be decidable: we have no
proof one way or the other, in spite of for decades having thought we
had some.

[toc] | [prev] | [next] | [standalone]


#2003 — Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-30 19:30 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<pcmdnZn7zqICAVjCnZ2dnUU7-aOdnZ2d@giganews.com>
In reply to#2002
On 11/30/2020 7:23 PM, Kaz Kylheku wrote:
> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>> On 11/30/2020 4:48 PM, Kaz Kylheku wrote:
>>> ["Followup-To:" header set to comp.theory.]
>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>> On 11/30/2020 3:06 PM, Kaz Kylheku wrote:
>>>>> On 2020-11-30, olcott <NoOne@NoWhere.com> wrote:
>>>>>>> You still haven't explained how your non-halting decider can decide if
>>>>>>> an arbitrary program given arbitrary input halts.
>>>>>>
>>>>>> My goal is not to actually solve the halting problem because to do this
>>>>>> I would have to write a computer program that is ALL-KNOWING.
>>>>>
>>>>> An imaginary "all knowing" entity is called an "oracle".
>>>>>
>>>>> You believe that calculating halting requires an "oracle" program;
>>>>> yet you don't see that as an impediment against computability?
>>>>>
>>>>
>>>> I already posted the complete execution trace of the details of how
>>>> Halts decides halting on H_Hat()
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>>      u32 Input_Halts = Halts(P, P);
>>>>      if (!Input_Halts)
>>>>        HALT
>>>>      else
>>>>        HERE: goto HERE;
>>>> }
>>>>
>>>> When Halts() always simulates its input it is obvious that
>>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion thus can be
>>>> decided as non halting.
>>>
>>> You're blind to the obvious issue that H_Hat isn't a single
>>> function/program. It's a *class* of programs.
>>>
>>
>> Every element of this class (where Halts() bases its decision on
>> simulating its input) specifies infinite recursion.
> 
> Firstly, you don't yet understand what it means to decide halting.
> 

This example proves that you are wrong !

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

void H_Hat(u32 P)
{
   u32 Aborted = DebugTrace(P, P);
   if (Aborted)
     HALT
   else
     HERE: goto HERE;
}

int main()
{
   u32 P = (u32)H_Hat;
   DebugTrace(P, P);
   HALT;
}


I am stopping at your first mistake because you are not bothering to pay 
any attention what-so-ever to what I just said.

-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1939

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 12:46 -0600
Message-ID<PsOdneY9RaQb1FzCnZ2dnUU7-cXNnZ2d@giganews.com>
In reply to#1932
On 11/27/2020 12:03 PM, Richard Damon wrote:
> On 11/27/20 12:10 PM, olcott wrote:
>> On 11/27/2020 10:57 AM, Mr Flibble wrote:
>>> On 27/11/2020 16:52, olcott wrote:
>>>> On 10/19/2020 12:45 PM, olcott wrote:
>>>>> x86utm is a universal Turing Machine having the x86 language as
>>>>> machine description language. It can directly execute the COFF
>>>>> object file output of the Microsoft "C" compiler as long as the code
>>>>> does not invoke any external libraries. All global data must be
>>>>> initialized or it does not exist in the COFF object file. All
>>>>> relocatable refernces are patched to point to their file offsets.
>>>>>
>>>>> This was the most difficult aspect of the entire x86utm system:
>>>>> The operating system function DebugStep() can now invoke itself
>>>>> recursively to an arbitrary depth.
>>>>>
>>>>> It can DebugStep() itself DebugStep()ing itself...
>>>>> DebugStep()ing another function with an arbitrary hierarchy of
>>>>> DebugStep()ing in-between.
>>>>>
>>>>> The halt decider aborts the execution of its target function and
>>>>> reports not halting behavior as soon as it detects that its target
>>>>> function would not otherwise halt. Without a DebugStep() function
>>>>> its examination of the Target code wold be insufficiently granular.
>>>>>
>>>>> The code that correctly decides the conventional self-referential
>>>>> halting problem counter-examples can now finally be written. This
>>>>> code utterly depended upon the now finally completed DebugStep()
>>>>> operating system function.
>>>>>
>>>>> This code exploits a key undiscovered aspect that is common to all
>>>>> the conventional self-referential halting problem counter-examples.
>>>>>
>>>>> This key undiscovered aspect that makes all of the conventional
>>>>> self-referential halting problem counter-examples decidable cannot
>>>>> simply be dismissed out-of-hand without review when a fully
>>>>> operational program shows that it does correctly decide elements of
>>>>> the set of of conventional self-referential halting problem
>>>>> counter-examples.
>>>
>>> You still haven't shown how non-halting behaviour is decided.
>>>
>>> Still nothing to see here.
>>>
>>> /Flibble
>>>
>>
>> I have explained how non-halting is decided in complete detail many
>> times. It turns out that the complete detail is so simple that no-one
>> accepted that it was complete until I proved that it is complete to
>> Mike. Here is the proof.
>>
>> The sequences of instructions from HERE to THERE and HERE to HERE are
>> from actual execution traces. The x86 emulator screens out all dead code
>> and only shows us the precise sequence of the code that is actually
>> reached.
>>
>> -HERE:  // current location
>> -   Instructions that cannot possibly exit a loop
>> -THERE: goto HERE;
>>
>> To form a mathematical proof on the basis of the x86 language being
>> construed as a formal language we only have to derive the complete list
>> of every instruction that can possibly exit the above loop and if there
>> are none of these between the labels HERE and THERE then we know that
>> the loop is infinite.
>>
>> The case for infinite recursion is similar.
>>
>> -HERE: Call Function At Address X
>> -   Instructions that cannot possibly exit recursion
>> -HERE: Call Function At Address X
>>
>> If there are no instructions that can possibly exit recursion between
>> invocations of the same function from the same machine address, then
>> recursion is infinite.
>>
> 
> Yes, infinite recursion with NO conditional is an infinite loop. When
> those instruction are executed inside a virtual machine that contains
> code that might decide to terminate that loop, then HAS a conditional in
> the ACTUAL execution trace of the processor.

It looks like I have to tell you the same thing an average of 
twenty-five times before you ever hear it for the very first time:

HERE IT IS AGAIN:
Any input (TMD / DATA) that would never halt unless its simulator 
stopped simulating it expresses behavior that is not halting behavior.

Halts decides that H_Hat would never halt unless Halts stopped 
simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false.



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1951

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 15:40 -0600
Message-ID<6vSdnaJBrcGv71zCnZ2dnUU7-SnNnZ2d@giganews.com>
In reply to#1939
On 11/27/2020 3:28 PM, Richard Damon wrote:
> On 11/27/20 1:46 PM, olcott wrote:
>> On 11/27/2020 12:03 PM, Richard Damon wrote:
> 
>>>
>>> Yes, infinite recursion with NO conditional is an infinite loop. When
>>> those instruction are executed inside a virtual machine that contains
>>> code that might decide to terminate that loop, then HAS a conditional in
>>> the ACTUAL execution trace of the processor.
>>
>> It looks like I have to tell you the same thing an average of
>> twenty-five times before you ever hear it for the very first time:
>>
>> HERE IT IS AGAIN:
>> Any input (TMD / DATA) that would never halt unless its simulator
>> stopped simulating it expresses behavior that is not halting behavior.
>>
>> Halts decides that H_Hat would never halt unless Halts stopped
>> simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false.
>>
> 
> And you STILL refuse to look at the actual behavior.
> 
> Yes, any input (Turing Machine Description / Data) that would never halt
> unless its simulator stopped simulating it expresses behavior that is
> not halting.
> 
> The problem is that when we actually TEST this, we see that, in the case
> of H_Hat it does halt.
> 
ONLY BECAUSE ITS SIMULATOR STOPPED SIMULATING IT, thus leaving no chance 
what-so-ever for any correct rebuttal.

Why you persist in incorrect rebuttals I will never know, it sure seems 
quite foolish to me.

Perhaps you really do have attention deficit disorder and we have to go 
through this twenty more times before you get it.


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1952

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 15:52 -0600
Message-ID<1JOdnQuvENeH6FzCnZ2dnUU7-cvNnZ2d@giganews.com>
In reply to#1951
On 11/27/2020 3:40 PM, olcott wrote:
> On 11/27/2020 3:28 PM, Richard Damon wrote:
>> On 11/27/20 1:46 PM, olcott wrote:
>>> On 11/27/2020 12:03 PM, Richard Damon wrote:
>>
>>>>
>>>> Yes, infinite recursion with NO conditional is an infinite loop. When
>>>> those instruction are executed inside a virtual machine that contains
>>>> code that might decide to terminate that loop, then HAS a 
>>>> conditional in
>>>> the ACTUAL execution trace of the processor.
>>>
>>> It looks like I have to tell you the same thing an average of
>>> twenty-five times before you ever hear it for the very first time:
>>>
>>> HERE IT IS AGAIN:
>>> Any input (TMD / DATA) that would never halt unless its simulator
>>> stopped simulating it expresses behavior that is not halting behavior.
>>>
>>> Halts decides that H_Hat would never halt unless Halts stopped
>>> simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false.
>>>
>>
>> And you STILL refuse to look at the actual behavior.
>>
>> Yes, any input (Turing Machine Description / Data) that would never halt
>> unless its simulator stopped simulating it expresses behavior that is
>> not halting.
>>
>> The problem is that when we actually TEST this, we see that, in the case
>> of H_Hat it does halt.
>>
> ONLY BECAUSE ITS SIMULATOR STOPPED SIMULATING IT, thus leaving no chance 
> what-so-ever for any correct rebuttal.
> 
> Why you persist in incorrect rebuttals I will never know, it sure seems 
> quite foolish to me.
> 
> Perhaps you really do have attention deficit disorder and we have to go 
> through this twenty more times before you get it.

We are not asking:
Does Halts(H_Hat, H_Hat) halt?

We are asking:
Does this input (H_Hat, H_Hat) to Halts have to be aborted?


-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [next] | [standalone]


#1953

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 17:09 -0600
Message-ID<ocmdndSIT4-6GlzCnZ2dnUU7-L-dnZ2d@giganews.com>
In reply to#1951
On 11/27/2020 4:09 PM, Richard Damon wrote:
> On 11/27/20 4:40 PM, olcott wrote:
>> On 11/27/2020 3:28 PM, Richard Damon wrote:
>>> On 11/27/20 1:46 PM, olcott wrote:
>>>> On 11/27/2020 12:03 PM, Richard Damon wrote:
>>>
>>>>>
>>>>> Yes, infinite recursion with NO conditional is an infinite loop. When
>>>>> those instruction are executed inside a virtual machine that contains
>>>>> code that might decide to terminate that loop, then HAS a
>>>>> conditional in
>>>>> the ACTUAL execution trace of the processor.
>>>>
>>>> It looks like I have to tell you the same thing an average of
>>>> twenty-five times before you ever hear it for the very first time:
>>>>
>>>> HERE IT IS AGAIN:
>>>> Any input (TMD / DATA) that would never halt unless its simulator
>>>> stopped simulating it expresses behavior that is not halting behavior.
>>>>
>>>> Halts decides that H_Hat would never halt unless Halts stopped
>>>> simulating H_Hat ∴ Halts(H_Hat, H_Hat) == false.
>>>>
>>>
>>> And you STILL refuse to look at the actual behavior.
>>>
>>> Yes, any input (Turing Machine Description / Data) that would never halt
>>> unless its simulator stopped simulating it expresses behavior that is
>>> not halting.
>>>
>>> The problem is that when we actually TEST this, we see that, in the case
>>> of H_Hat it does halt.
>>>
>> ONLY BECAUSE ITS SIMULATOR STOPPED SIMULATING IT, thus leaving no chance
>> what-so-ever for any correct rebuttal.
>>
>> Why you persist in incorrect rebuttals I will never know, it sure seems
>> quite foolish to me.
>>
>> Perhaps you really do have attention deficit disorder and we have to go
>> through this twenty more times before you get it.
>>
>>
> 

Any input (TMD / DATA) that would never halt unless its simulator
stopped simulating it expresses behavior that is not halting behavior.

Thus proving beyond all possible doubt that Halts necessarily made a 
correct not halting decision when it decided to stop simulating H_Hat.

We are not asking:
Does Halts(H_Hat, H_Hat) halt?

We are asking:
Does this input (H_Hat, H_Hat) to Halts have to be aborted?



-- 
Copyright 2020 Pete Olcott

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

[toc] | [prev] | [standalone]


Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | comp.software-eng


csiph-web