Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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 |
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
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