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


Groups > comp.theory > #26101

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

Subject Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Newsgroups comp.theory
References <b7ydnfw7a_chTRDCnZ2dnUU7-SPNnZ2d@giganews.com> <fOydnUUZrd5Gs1zCnZ2dnUU7-Y3NnZ2d@giganews.com> <eeawH.150037$b5kb.121611@fx15.ams4> <jLSdncNvGeKGrlzCnZ2dnUU7-I3NnZ2d@giganews.com>
From Richard Damon <Richard@Damon-Family.org>
Message-ID <ecbwH.923$PP.154@fx07.iad> (permalink)
Organization Forte - www.forteinc.com
Date 2020-11-27 13:03 -0500

Show all headers | View raw


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.

If a program calls the Halt Decider insider of itself, that conditional
inside the Halt Decider counts, as far as checking if that outer program
has infinite behavior. This comes out as part of the Halt Deciders
requirement to make its decision in finite time. It is impossible for a
(working) Halt Decider to create non-halting behavior in the code that
uses it (unless the outer program tries to call that Halt Decider an
infinite number of times in that outer program, but then that loop would
be detectable in that outer program).

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 12:45 -0500
  Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-19 20:04 +0100
    Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 14:15 -0500
      Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-19 21:34 +0100
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 15:50 -0500
          Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-19 22:09 +0100
            Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 16:28 -0500
              Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-19 23:13 +0100
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 17:54 -0500
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-20 00:41 +0100
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Richard Damon <Richard@Damon-Family.org> - 2020-10-19 21:15 -0400
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 20:18 -0500
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-20 02:38 +0100
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-10-20 04:35 -0700
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-20 13:27 +0100
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-20 11:31 +0100
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)[ KEY ] olcott <NoOne@NoWhere.com> - 2020-10-20 11:07 -0500
        Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Eli the Bearded <*@eli.users.panix.com> - 2020-10-19 21:04 +0000
          Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-19 22:46 +0100
            Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Eli the Bearded <*@eli.users.panix.com> - 2020-10-19 21:52 +0000
              Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-10-19 23:48 +0100
              Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 18:03 -0500
            Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Jeff Barnett <jbb@notatt.com> - 2020-10-19 21:26 -0600
          Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-10-19 14:54 -0700
            Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-10-19 14:57 -0700
              Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) R Kym Horsell <kym@kymhorsell.com> - 2020-10-19 22:17 +0000
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-10-19 16:25 -0700
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) R Kym Horsell <kym@kymhorsell.com> - 2020-10-19 23:29 +0000
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) David Kleinecke <dkleinecke@gmail.com> - 2020-10-19 18:19 -0700
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-10-19 18:26 -0700
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-10-19 16:34 -0700
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) R Kym Horsell <kym@kymhorsell.com> - 2020-10-20 00:08 +0000
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Richard Damon <Richard@Damon-Family.org> - 2020-10-19 21:12 -0400
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-10-21 20:23 -0700
  Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-19 20:39 +0100
    Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) olcott <NoOne@NoWhere.com> - 2020-10-19 14:54 -0500
      Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-10-19 21:49 +0100
  Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(39 days of review and no mistakes found) olcott <NoOne@NoWhere.com> - 2020-11-27 10:52 -0600
    Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(39 days of review and no mistakes found) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-27 16:57 +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: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 ) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 13:24 -0500
              Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-27 19:08 +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 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 ) Mike Terry <news.dead.person.stones@darjeeling.plus.com> - 2020-11-27 21:04 +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 15:24 -0600
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-28 03:29 +0000
                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) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-11-30 01:42 +0000
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) olcott <NoOne@NoWhere.com> - 2020-11-29 20:40 -0600
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding) Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2020-11-30 17:25 +0000
                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) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-12-01 04:00 -0800
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) olcott <NoOne@NoWhere.com> - 2020-12-01 09:13 -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 17:32 +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 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 15:49 -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 22:22 +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) Richard Damon <Richard@Damon-Family.org> - 2020-12-01 21:51 -0500
                Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face) Andy Walker <anw@cuboid.co.uk> - 2020-12-01 15:22 +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 09:33 -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:14 +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:37 -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 12:56 -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 ) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 13:03 -0500
          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 ) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 16:28 -0500
              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 ) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 17:17 -0500
                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:20 -0600
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 21:27 -0500
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 17:09 -0500
                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
                Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting ) Richard Damon <Richard@Damon-Family.org> - 2020-11-27 21:51 -0500

csiph-web