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


Groups > comp.theory > #23988 > unrolled thread

The key aspects of x86utm are now finally complete (Refuting the HP proofs)

Started byolcott <NoOne@NoWhere.com>
First post2020-10-19 12:45 -0500
Last post2020-11-27 21:51 -0500
Articles 20 on this page of 97 — 14 participants

Back to article view | Back to comp.theory


Contents

  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

Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →


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

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2020-11-27 17:24 +0000
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<xDawH.48368$%m67.27765@fx02.ams4>
In reply to#26096
On 27/11/2020 17:10, 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.

Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't sufficient to decide non-halting behaviour for an arbitrary program given arbitrary input.

/Flibble

-- 
¬

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 11:54 -0600
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<aqudnTRmQ87RoFzCnZ2dnUU7-QnNnZ2d@giganews.com>
In reply to#26097
On 11/27/2020 11:24 AM, Mr Flibble wrote:
> On 27/11/2020 17:10, 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.
> 
> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't 
> sufficient to decide non-halting behaviour for an arbitrary program 
> given arbitrary input.
> 
> /Flibble
> 

It is sufficient to definitively decide all of the non-halting cases 
meeting the above criteria including this one:

void H_Hat(u32 P)
{
   u32 Would_Halt = Halts(P, P);
   if (!Would_Halt)
     HALT
   else
     HERE: goto HERE;
}

Halts(H_Hat, H_Hat);

The above code (computationally equivalent to all of the conventional 
halting probem proof counter-examples) is provably decidable by the 
criteria provided.

-- 
Copyright 2020 Pete Olcott

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

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


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

FromRichard Damon <Richard@Damon-Family.org>
Date2020-11-27 13:24 -0500
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<JvbwH.9395$jL.5315@fx13.iad>
In reply to#26100
On 11/27/20 12:54 PM, olcott wrote:
> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>> On 27/11/2020 17:10, 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.
>>
>> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
>> sufficient to decide non-halting behaviour for an arbitrary program
>> given arbitrary input.
>>
>> /Flibble
>>
> 
> It is sufficient to definitively decide all of the non-halting cases
> meeting the above criteria including this one:
> 
> void H_Hat(u32 P)
> {
>   u32 Would_Halt = Halts(P, P);
>   if (!Would_Halt)
>     HALT
>   else
>     HERE: goto HERE;
> }
> 
> Halts(H_Hat, H_Hat);
> 
> The above code (computationally equivalent to all of the conventional
> halting probem proof counter-examples) is provably decidable by the
> criteria provided.
> 

Except that if we look at the FULL trace of the problem execution of
H_Hat, we see conditionals in the loop.

Trace that the top level halts (Halts#1) will see:

1) Enter H_Hat #1
2) Call Halts #2 (Note, Halts#2 behavior is part of H_Hat#1)
3) Halt#2 Asks are we Looping? No
4) Setup machine H_Hat#2
5) Halt#2 Asks are we Looping? No
6) Enter H_Hat #2
7) Halt#2 Asks are we Looping? No
8) Setup Machine H_Hat#3
9) Halt#2 Asks are we Looping? No
10) H_Hat#2 calls Halts #3
11) Halt#2 and Halts#3 Asks are we Looping? No
12) Enter H_Hat #3
13) Halt#2 and Halts#3  Asks are we Looping? No
14) H_Hat#3 calls Halts #4
...

The key facts is that ALL execution inside a Halts called inside the
program under inspection is conditioned by that Halt Decider is it has a
requirement to maintain finite execution.

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


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

FromMike Terry <news.dead.person.stones@darjeeling.plus.com>
Date2020-11-27 19:08 +0000
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<RuednZCOCPhR01zCnZ2dnUU78UnNnZ2d@brightview.co.uk>
In reply to#26103
On 27/11/2020 18:24, Richard Damon wrote:
> On 11/27/20 12:54 PM, olcott wrote:
>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>> On 27/11/2020 17:10, 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.
>>>
>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
>>> sufficient to decide non-halting behaviour for an arbitrary program
>>> given arbitrary input.
>>>
>>> /Flibble
>>>
>>
>> It is sufficient to definitively decide all of the non-halting cases
>> meeting the above criteria including this one:
>>
>> void H_Hat(u32 P)
>> {
>>   u32 Would_Halt = Halts(P, P);
>>   if (!Would_Halt)
>>     HALT
>>   else
>>     HERE: goto HERE;
>> }
>>
>> Halts(H_Hat, H_Hat);
>>
>> The above code (computationally equivalent to all of the conventional
>> halting probem proof counter-examples) is provably decidable by the
>> criteria provided.
>>
>
> Except that if we look at the FULL trace of the problem execution of
> H_Hat, we see conditionals in the loop.
>

Maybe so, but - the whole issue of "conditionals in the loop" is a bogus 
issue.  The underlying test for infinite recursion IS JUST WRONG.  I.e. 
the whole "no conditionals in the loop" idea doesn't work.  So 
demonstrating there really are "missed conditionals in the loop" is a 
red herring.

In a way it's a good thing that PO has picked up on this aspect, and 
delivered his "proof" that he is right - because he is WRONG and now has 
pinned his colours to the mast in a way that can easily be SHOWN to be 
wrong.  This will reveal that PO is a complete DUFFER who's incapable of 
delivering anything of value in such a technical area.  When that 
happens, I don't expect PO to acknowledge anything of course, so it 
won't really make much difference to this newsgroup.

When I get some time, I'll start a new thread on why PO's "proof" is 
duff, if nobody else has done it by then.  (Right now I have other 
things to do.)

Mike.

> Trace that the top level halts (Halts#1) will see:
>
> 1) Enter H_Hat #1
> 2) Call Halts #2 (Note, Halts#2 behavior is part of H_Hat#1)
> 3) Halt#2 Asks are we Looping? No
> 4) Setup machine H_Hat#2
> 5) Halt#2 Asks are we Looping? No
> 6) Enter H_Hat #2
> 7) Halt#2 Asks are we Looping? No
> 8) Setup Machine H_Hat#3
> 9) Halt#2 Asks are we Looping? No
> 10) H_Hat#2 calls Halts #3
> 11) Halt#2 and Halts#3 Asks are we Looping? No
> 12) Enter H_Hat #3
> 13) Halt#2 and Halts#3  Asks are we Looping? No
> 14) H_Hat#3 calls Halts #4
> ...
>
> The key facts is that ALL execution inside a Halts called inside the
> program under inspection is conditioned by that Halt Decider is it has a
> requirement to maintain finite execution.
>

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 13:34 -0600
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<eZednUauDfsiyVzCnZ2dnUU7-N_NnZ2d@giganews.com>
In reply to#26111
On 11/27/2020 1:08 PM, Mike Terry wrote:
> On 27/11/2020 18:24, Richard Damon wrote:
>> On 11/27/20 12:54 PM, olcott wrote:
>>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>>> On 27/11/2020 17:10, 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.
>>>>
>>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
>>>> sufficient to decide non-halting behaviour for an arbitrary program
>>>> given arbitrary input.
>>>>
>>>> /Flibble
>>>>
>>>
>>> It is sufficient to definitively decide all of the non-halting cases
>>> meeting the above criteria including this one:
>>>
>>> void H_Hat(u32 P)
>>> {
>>>   u32 Would_Halt = Halts(P, P);
>>>   if (!Would_Halt)
>>>     HALT
>>>   else
>>>     HERE: goto HERE;
>>> }
>>>
>>> Halts(H_Hat, H_Hat);
>>>
>>> The above code (computationally equivalent to all of the conventional
>>> halting probem proof counter-examples) is provably decidable by the
>>> criteria provided.
>>>
>>
>> Except that if we look at the FULL trace of the problem execution of
>> H_Hat, we see conditionals in the loop.
>>
> 
> Maybe so, but - the whole issue of "conditionals in the loop" is a bogus 
> issue.  The underlying test for infinite recursion IS JUST WRONG.  I.e. 
> the whole "no conditionals in the loop" idea doesn't work.  So 
> demonstrating there really are "missed conditionals in the loop" is a 
> red herring.
> 
> In a way it's a good thing that PO has picked up on this aspect, and 
> delivered his "proof" that he is right - because he is WRONG and now has 
> pinned his colours to the mast in a way that can easily be SHOWN to be 
> wrong.  This will reveal that PO is a complete DUFFER who's incapable of 
> delivering anything of value in such a technical area.  When that 
> happens, I don't expect PO to acknowledge anything of course, so it 
> won't really make much difference to this newsgroup.
> 
Mere empty rhetoric utterly bereft of any actual reasoning.

I did not expect you to stoop to this level of tactics, this is the sort 
of thing that Ben does.

If you can provide a valid counter-example feel free. To the best of my 
knowledge valid counter-examples are categorically impossible.

Every "counter-example" so far has at best been the straw-man error of 
reasoning.




If you understand the basic principle that a TMD simulated by a UTM is 
computationally equivalent to the direct execution of a TM then you 
would understand that:

(a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
is computationally equivalent to

(b) TM1 executing TM2 executing TM1 executing TM2

Thus your RECURSIVE EMULATIONS, are shown to have no effect on the 
actual computation.


-- 
Copyright 2020 Pete Olcott

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

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 14:04 -0600
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<5O2dnZEAp4wwxlzCnZ2dnUU7-YvNnZ2d@giganews.com>
In reply to#26114
On 11/27/2020 1:34 PM, olcott wrote:
> On 11/27/2020 1:08 PM, Mike Terry wrote:
>> On 27/11/2020 18:24, Richard Damon wrote:
>>> On 11/27/20 12:54 PM, olcott wrote:
>>>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>>>> On 27/11/2020 17:10, 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.
>>>>>
>>>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
>>>>> sufficient to decide non-halting behaviour for an arbitrary program
>>>>> given arbitrary input.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> It is sufficient to definitively decide all of the non-halting cases
>>>> meeting the above criteria including this one:
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>>   u32 Would_Halt = Halts(P, P);
>>>>   if (!Would_Halt)
>>>>     HALT
>>>>   else
>>>>     HERE: goto HERE;
>>>> }
>>>>
>>>> Halts(H_Hat, H_Hat);
>>>>
>>>> The above code (computationally equivalent to all of the conventional
>>>> halting probem proof counter-examples) is provably decidable by the
>>>> criteria provided.
>>>>
>>>
>>> Except that if we look at the FULL trace of the problem execution of
>>> H_Hat, we see conditionals in the loop.
>>>
>>
>> Maybe so, but - the whole issue of "conditionals in the loop" is a 
>> bogus issue.  The underlying test for infinite recursion IS JUST 
>> WRONG.  I.e. the whole "no conditionals in the loop" idea doesn't 
>> work.  So demonstrating there really are "missed conditionals in the 
>> loop" is a red herring.
>>
>> In a way it's a good thing that PO has picked up on this aspect, and 
>> delivered his "proof" that he is right - because he is WRONG and now 
>> has pinned his colours to the mast in a way that can easily be SHOWN 
>> to be wrong.  This will reveal that PO is a complete DUFFER who's 
>> incapable of delivering anything of value in such a technical area.  
>> When that happens, I don't expect PO to acknowledge anything of 
>> course, so it won't really make much difference to this newsgroup.
>>
> Mere empty rhetoric utterly bereft of any actual reasoning.
> 
> I did not expect you to stoop to this level of tactics, this is the sort 
> of thing that Ben does.
> 
> If you can provide a valid counter-example feel free. To the best of my 
> knowledge valid counter-examples are categorically impossible.
> 
> Every "counter-example" so far has at best been the straw-man error of 
> reasoning.
> 
> 
> 
> 
> If you understand the basic principle that a TMD simulated by a UTM is 
> computationally equivalent to the direct execution of a TM then you 
> would understand that:
> 
> (a) UTM1 simulating <UTM2> simulating <UTM1> simulating <UTM2>
> is computationally equivalent to
> 
> (b) TM1 executing TM2 executing TM1 executing TM2
> 
> Thus your RECURSIVE EMULATIONS, are shown to have no effect on the 
> actual computation.

Thus when I simply screen out all of the emulator instructions and only 
focus on the emulated instructions I am only screening out instructions 
that have no effect on the actual computation what-so-ever.

Output_Debug_Trace() [00010bc4]  size(148)  capacity(65536)
[000005a4](01)  55                  push ebp
[000005a5](02)  8bec                mov ebp,esp
[000005a7](01)  51                  push ecx
[000005a8](07)  c745fc74050000      mov [ebp-04],00000574
[000005af](03)  8b45fc              mov eax,[ebp-04]
[000005b2](01)  50                  push eax
[000005b3](03)  8b4dfc              mov ecx,[ebp-04]
[000005b6](01)  51                  push ecx
[000005b7](05)  e898fdffff          call 00000354   	----CALL[00000354]
[00000574](01)  55                  push ebp
[00000575](02)  8bec                mov ebp,esp
[00000577](01)  51                  push ecx
[00000578](03)  8b4508              mov eax,[ebp+08]
[0000057b](01)  50                  push eax
[0000057c](03)  8b4d08              mov ecx,[ebp+08]
[0000057f](01)  51                  push ecx
[00000580](05)  e8cffdffff          call 00000354   	----CALL[00000354]
[00000574](01)  55                  push ebp
[00000575](02)  8bec                mov ebp,esp
[00000577](01)  51                  push ecx
[00000578](03)  8b4508              mov eax,[ebp+08]
[0000057b](01)  50                  push eax
[0000057c](03)  8b4d08              mov ecx,[ebp+08]
[0000057f](01)  51                  push ecx
[00000580](05)  e8cffdffff          call 00000354   	----CALL[00000354]




-- 
Copyright 2020 Pete Olcott

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

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


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

FromMike Terry <news.dead.person.stones@darjeeling.plus.com>
Date2020-11-27 21:04 +0000
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<hYidnTF8kvRq9FzCnZ2dnUU78R_NnZ2d@brightview.co.uk>
In reply to#26114
On 27/11/2020 19:34, olcott wrote:
> On 11/27/2020 1:08 PM, Mike Terry wrote:
>> On 27/11/2020 18:24, Richard Damon wrote:
>>> On 11/27/20 12:54 PM, olcott wrote:
>>>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>>>> On 27/11/2020 17:10, 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.
>>>>>
>>>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation isn't
>>>>> sufficient to decide non-halting behaviour for an arbitrary program
>>>>> given arbitrary input.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> It is sufficient to definitively decide all of the non-halting cases
>>>> meeting the above criteria including this one:
>>>>
>>>> void H_Hat(u32 P)
>>>> {
>>>>   u32 Would_Halt = Halts(P, P);
>>>>   if (!Would_Halt)
>>>>     HALT
>>>>   else
>>>>     HERE: goto HERE;
>>>> }
>>>>
>>>> Halts(H_Hat, H_Hat);
>>>>
>>>> The above code (computationally equivalent to all of the conventional
>>>> halting probem proof counter-examples) is provably decidable by the
>>>> criteria provided.
>>>>
>>>
>>> Except that if we look at the FULL trace of the problem execution of
>>> H_Hat, we see conditionals in the loop.
>>>
>>
>> Maybe so, but - the whole issue of "conditionals in the loop" is a
>> bogus issue.  The underlying test for infinite recursion IS JUST
>> WRONG.  I.e. the whole "no conditionals in the loop" idea doesn't
>> work.  So demonstrating there really are "missed conditionals in the
>> loop" is a red herring.
>>
>> In a way it's a good thing that PO has picked up on this aspect, and
>> delivered his "proof" that he is right - because he is WRONG and now
>> has pinned his colours to the mast in a way that can easily be SHOWN
>> to be wrong.  This will reveal that PO is a complete DUFFER who's
>> incapable of delivering anything of value in such a technical area.
>> When that happens, I don't expect PO to acknowledge anything of
>> course, so it won't really make much difference to this newsgroup.
>>
> Mere empty rhetoric utterly bereft of any actual reasoning.
>
> I did not expect you to stoop to this level of tactics, this is the sort
> of thing that Ben does.
>

I was replying to Richard, not you.  I was not "arguing" with you, just 
pointing out something Richard may not (or may) have realised.  If 
Richard wants me to clarify, then he can ask questions, and also I've 
said elsewhere that at some point I'll start a new thread on the topic 
(but I'm busy at the moment).

Meanwhile in direct responses to your claim I've pointed out why your 
"proof" isn't a proof at all, and I've pointed out the nature of your 
mistake:  you don't understand the difference between recursive CALLs 
and recursive EMULATIONS.  Your explanation as to why there's no 
difference just doesn't work, for reasons I've given.  In the end, 
you're reduced to just saying over and over "it's true and I've proved it".

> If you can provide a valid counter-example feel free. To the best of my
> knowledge valid counter-examples are categorically impossible.

If YOU make a claim, it's up to you to prove it, not up to others to 
hunt around for counterexamples.  (But I'll probably put one in the new 
thread if/when I start it.)

Mike.

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 15:24 -0600
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<a82dnd0yv6Xm81zCnZ2dnUU7-IvNnZ2d@giganews.com>
In reply to#26123
On 11/27/2020 3:04 PM, Mike Terry wrote:
> On 27/11/2020 19:34, olcott wrote:
>> On 11/27/2020 1:08 PM, Mike Terry wrote:
>>> On 27/11/2020 18:24, Richard Damon wrote:
>>>> On 11/27/20 12:54 PM, olcott wrote:
>>>>> On 11/27/2020 11:24 AM, Mr Flibble wrote:
>>>>>> On 27/11/2020 17:10, 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.
>>>>>>
>>>>>> Semantic analysis of HERE to THERE and HERE to HERE in isolation 
>>>>>> isn't
>>>>>> sufficient to decide non-halting behaviour for an arbitrary program
>>>>>> given arbitrary input.
>>>>>>
>>>>>> /Flibble
>>>>>>
>>>>>
>>>>> It is sufficient to definitively decide all of the non-halting cases
>>>>> meeting the above criteria including this one:
>>>>>
>>>>> void H_Hat(u32 P)
>>>>> {
>>>>>   u32 Would_Halt = Halts(P, P);
>>>>>   if (!Would_Halt)
>>>>>     HALT
>>>>>   else
>>>>>     HERE: goto HERE;
>>>>> }
>>>>>
>>>>> Halts(H_Hat, H_Hat);
>>>>>
>>>>> The above code (computationally equivalent to all of the conventional
>>>>> halting probem proof counter-examples) is provably decidable by the
>>>>> criteria provided.
>>>>>
>>>>
>>>> Except that if we look at the FULL trace of the problem execution of
>>>> H_Hat, we see conditionals in the loop.
>>>>
>>>
>>> Maybe so, but - the whole issue of "conditionals in the loop" is a
>>> bogus issue.  The underlying test for infinite recursion IS JUST
>>> WRONG.  I.e. the whole "no conditionals in the loop" idea doesn't
>>> work.  So demonstrating there really are "missed conditionals in the
>>> loop" is a red herring.
>>>
>>> In a way it's a good thing that PO has picked up on this aspect, and
>>> delivered his "proof" that he is right - because he is WRONG and now
>>> has pinned his colours to the mast in a way that can easily be SHOWN
>>> to be wrong.  This will reveal that PO is a complete DUFFER who's
>>> incapable of delivering anything of value in such a technical area.
>>> When that happens, I don't expect PO to acknowledge anything of
>>> course, so it won't really make much difference to this newsgroup.
>>>
>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>
>> I did not expect you to stoop to this level of tactics, this is the sort
>> of thing that Ben does.
>>
> 
> I was replying to Richard, not you.  

I will pay closer attention to that.

> I was not "arguing" with you, just 
> pointing out something Richard may not (or may) have realised.  If 
> Richard wants me to clarify, then he can ask questions, and also I've 
> said elsewhere that at some point I'll start a new thread on the topic 
> (but I'm busy at the moment).
> 
> Meanwhile in direct responses to your claim I've pointed out why your 
> "proof" isn't a proof at all, and I've pointed out the nature of your 
> mistake:  you don't understand the difference between recursive CALLs 
> and recursive EMULATIONS.  

That the UTM emulation of a TMD of A TM is computationally equivalent to 
the direct execution of this same TM proves:

When <A> emulates <B> emulates <A>
this is computationally equivalent to
A calls B calls A


> Your explanation as to why there's no 
> difference just doesn't work, for reasons I've given.  In the end, 
> you're reduced to just saying over and over "it's true and I've proved it".
> 
>> If you can provide a valid counter-example feel free. To the best of my
>> knowledge valid counter-examples are categorically impossible.
> 
> If YOU make a claim, it's up to you to prove it, not up to others to 
> hunt around for counterexamples.  (But I'll probably put one in the new 
> thread if/when I start it.)
> 
> Mike.
> 

So far it merely seems like you are demonstrating a lack of sufficient 
knowledge of the equivalence that I just pointed out:

UTM1(<TM1>, DATA) ≡ TM1(DATA)
thus
UTM1(<UTM1>, (<TM1>, DATA)) ≡ TM1(TM1(DATA))



-- 
Copyright 2020 Pete Olcott

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

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


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

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2020-11-28 03:29 +0000
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(algorithm to decide not-halting )
Message-ID<87r1oe2m6v.fsf@bsb.me.uk>
In reply to#26114
olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:

> Mere empty rhetoric utterly bereft of any actual reasoning.
>
> I did not expect you to stoop to this level of tactics, this is the
> sort of thing that Ben does.

Here's the sort of "empty rhetoric utterly bereft of any actual
reasoning" that I post.  I challenged you to post a halt decider after a
clear definition from me of what I mean:

  A halt decider (in this context) is a function F such that F(P, I) is
  true if, and only if, P(I) is a finite computation and false
  otherwise.

You posted this:

  bool Halts(u32 P, u32 I)
  {
    bool Halted  = false;
    bool Aborted = false;
    while (!Halted && !Aborted)
    {
      Halted  = DebugStep(P, I);
      Aborted = Needs_To_Be_Aborted();
    }
    return !Aborted;
  }

and I then posted the confounding example:

  void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }

along with these two facts about it:

(a) Halts(Confound_Halts, Confound_Halts) returns false, and
(b) Confound_Halts(Confound_Halts) is a finite computation.

My conclusion was to ask:

  Therefore Halts is not a halt decider.  Which of the these do you
  disagree with?

Your response was to ignore these points and, instead, to give your own
defintion of what the right answer is, whilst carefuly avoiding saying
that it differed from mine (and everyone else's).

-- 
Ben.

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


#26146 — Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-27 21:57 -0600
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)
Message-ID<tvqdnQnZIdgWV1zCnZ2dnUU7-XvNnZ2d@giganews.com>
In reply to#26144
On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
> olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:
> 
>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>
>> I did not expect you to stoop to this level of tactics, this is the
>> sort of thing that Ben does.
> 
> Here's the sort of "empty rhetoric utterly bereft of any actual
> reasoning" that I post.  I challenged you to post a halt decider after a
> clear definition from me of what I mean:
> 
>    A halt decider (in this context) is a function F such that F(P, I) is
>    true if, and only if, P(I) is a finite computation and false
>    otherwise.

If you can have the discipline to very very carefully analyze my answers 
as if there was a real chance that I am correct then it should be quite 
easy to verify in your own mind that I am actually correct.

This is the key to understanding that I am correct.

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 > A computation that would not halt if its simulation were not
 > halted is indeed a non-halting computation.

When the simulator stops simulating H_Hat before H_Hat ever gets any 
return value from Halts this makes it impossible for H_Hat to do the 
opposite of whatever Halts decides, thus making all the conventional HP 
proofs lose their entire basis.



> You posted this:
> 
>    bool Halts(u32 P, u32 I)
>    {
>      bool Halted  = false;
>      bool Aborted = false;
>      while (!Halted && !Aborted)
>      {
>        Halted  = DebugStep(P, I);
>        Aborted = Needs_To_Be_Aborted();
>      }
>      return !Aborted;
>    }
> 
> and I then posted the confounding example:
> 
>    void Confound_Halts(u32 P) { if (Halts(P, P)) while (1); }
> 
> along with these two facts about it:
> 
> (a) Halts(Confound_Halts, Confound_Halts) returns false, and
> (b) Confound_Halts(Confound_Halts) is a finite computation.
> 
> My conclusion was to ask:
> 
>    Therefore Halts is not a halt decider.  Which of the these do you
>    disagree with?
> 
> Your response was to ignore these points and, instead, to give your own
> defintion of what the right answer is, whilst carefuly avoiding saying
> that it differed from mine (and everyone else's).
> 


-- 
Copyright 2020 Pete Olcott

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

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


#26208 — Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2020-11-30 01:42 +0000
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)
Message-ID<878saj1uyn.fsf@bsb.me.uk>
In reply to#26146
olcott <NoOne@NoWhere.com> writes:

> On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
>> olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:
>>
>>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>>
>>> I did not expect you to stoop to this level of tactics, this is the
>>> sort of thing that Ben does.
>>
>> Here's the sort of "empty rhetoric utterly bereft of any actual
>> reasoning" that I post.  I challenged you to post a halt decider after a
>> clear definition from me of what I mean:
>>
>>    A halt decider (in this context) is a function F such that F(P, I) is
>>    true if, and only if, P(I) is a finite computation and false
>>    otherwise.
>
> If you can have the discipline to very very carefully analyze my
> answers as if there was a real chance that I am correct then it should
> be quite easy to verify in your own mind that I am actually correct.

Yet another opportunity to accept the correct definition side stepped.
I ended up writing more but then saw that you had finally been clear
about my other questions so I am not sure this sub-thread really matters
any more.

<cut stuff you ignored here bue have have discussed elsewhere>
-- 
Ben.

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


#26212 — Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-29 20:40 -0600
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)
Message-ID<87qdncDHyLEDxlnCnZ2dnUU7-e_NnZ2d@giganews.com>
In reply to#26208
On 11/29/2020 7:42 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
>>> olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:
>>>
>>>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>>>
>>>> I did not expect you to stoop to this level of tactics, this is the
>>>> sort of thing that Ben does.
>>>
>>> Here's the sort of "empty rhetoric utterly bereft of any actual
>>> reasoning" that I post.  I challenged you to post a halt decider after a
>>> clear definition from me of what I mean:
>>>
>>>     A halt decider (in this context) is a function F such that F(P, I) is
>>>     true if, and only if, P(I) is a finite computation and false
>>>     otherwise.
>>
>> If you can have the discipline to very very carefully analyze my
>> answers as if there was a real chance that I am correct then it should
>> be quite easy to verify in your own mind that I am actually correct.
> 
> Yet another opportunity to accept the correct definition side stepped.
> I ended up writing more but then saw that you had finally been clear
> about my other questions so I am not sure this sub-thread really matters
> any more.
> 
> <cut stuff you ignored here bue have have discussed elsewhere>
> 

On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
 > A computation that would not halt if its simulation were not
 > halted is indeed a non-halting computation.

Just like there is no exception to this rule:
∀n ∈ ℕ ((n > 5) → (N > 3))

Every computation that would not halt unless its simulation was halted 
is by logical necessity a non-halting computation.

Both the x86 virtual machine computation and its simulated Turing 
machine description equivalent computation would never halt unless their 
simulator stopped simulating them.

In logic and mathematics, necessity and sufficiency are terms used to 
describe a conditional or implicational relationship between two 
statements. ... a sufficient condition is one which produces the said 
condition. https://en.wikipedia.org/wiki/Necessity_and_sufficiency

When-so-ever
A computation would not halt unless its simulation was halted
this computation is necessarily always a non-halting computation.
THE SUFFICIENCY CONDITION IS FULLY MET !!!

H_Hat <is> a computation that would not halt unless its simulation was 
halted ∴ (no matter how much you don't like it) H_Hat is a non-halting 
computation.





-- 
Copyright 2020 Pete Olcott

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

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


#26221 — Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2020-11-30 17:25 +0000
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)
Message-ID<3W9xH.74663$3L49.14501@fx24.ams4>
In reply to#26212
On 30/11/2020 02:40, olcott wrote:
> On 11/29/2020 7:42 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
>>>> olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:
>>>>
>>>>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>>>>
>>>>> I did not expect you to stoop to this level of tactics, this is the
>>>>> sort of thing that Ben does.
>>>>
>>>> Here's the sort of "empty rhetoric utterly bereft of any actual
>>>> reasoning" that I post.  I challenged you to post a halt decider after a
>>>> clear definition from me of what I mean:
>>>>
>>>>     A halt decider (in this context) is a function F such that F(P, I) is
>>>>     true if, and only if, P(I) is a finite computation and false
>>>>     otherwise.
>>>
>>> If you can have the discipline to very very carefully analyze my
>>> answers as if there was a real chance that I am correct then it should
>>> be quite easy to verify in your own mind that I am actually correct.
>>
>> Yet another opportunity to accept the correct definition side stepped.
>> I ended up writing more but then saw that you had finally been clear
>> about my other questions so I am not sure this sub-thread really matters
>> any more.
>>
>> <cut stuff you ignored here bue have have discussed elsewhere>
>>
> 
> On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
>  > A computation that would not halt if its simulation were not
>  > halted is indeed a non-halting computation.
> 
> Just like there is no exception to this rule:
> ∀n ∈ ℕ ((n > 5) → (N > 3))
> 
> Every computation that would not halt unless its simulation was halted is by logical necessity a non-halting computation.
> 
> Both the x86 virtual machine computation and its simulated Turing machine description equivalent computation would never halt unless their simulator stopped simulating them.
> 
> In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. ... a sufficient condition is one which produces the said condition. https://en.wikipedia.org/wiki/Necessity_and_sufficiency
> 
> When-so-ever
> A computation would not halt unless its simulation was halted
> this computation is necessarily always a non-halting computation.
> THE SUFFICIENCY CONDITION IS FULLY MET !!!
> 
> H_Hat <is> a computation that would not halt unless its simulation was halted ∴ (no matter how much you don't like it) H_Hat is a non-halting computation.

You still haven't explained how your non-halting decider can decide if an arbitrary program given arbitrary input halts.

Publish your working code (complete solution) so we can see past the guff and look at the actual implementation and then give it a test case that it fails to analyse correctly.

Until you produce a working implementation in the form of code all you have is conjecture; i.e. no refutation of the HP.

/Flibble

-- 
¬

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


#26222 — Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)

Fromolcott <NoOne@NoWhere.com>
Date2020-11-30 11:55 -0600
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)
Message-ID<oY2dnbTxTOKDr1jCnZ2dnUU7-QPNnZ2d@giganews.com>
In reply to#26221
On 11/30/2020 11:25 AM, Mr Flibble wrote:
> On 30/11/2020 02:40, olcott wrote:
>> On 11/29/2020 7:42 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> On 11/27/2020 9:29 PM, Ben Bacarisse wrote:
>>>>> olcott "Ĥ does not copy its input" <NoOne@NoWhere.com> writes:
>>>>>
>>>>>> Mere empty rhetoric utterly bereft of any actual reasoning.
>>>>>>
>>>>>> I did not expect you to stoop to this level of tactics, this is the
>>>>>> sort of thing that Ben does.
>>>>>
>>>>> Here's the sort of "empty rhetoric utterly bereft of any actual
>>>>> reasoning" that I post.  I challenged you to post a halt decider 
>>>>> after a
>>>>> clear definition from me of what I mean:
>>>>>
>>>>>     A halt decider (in this context) is a function F such that F(P, 
>>>>> I) is
>>>>>     true if, and only if, P(I) is a finite computation and false
>>>>>     otherwise.
>>>>
>>>> If you can have the discipline to very very carefully analyze my
>>>> answers as if there was a real chance that I am correct then it should
>>>> be quite easy to verify in your own mind that I am actually correct.
>>>
>>> Yet another opportunity to accept the correct definition side stepped.
>>> I ended up writing more but then saw that you had finally been clear
>>> about my other questions so I am not sure this sub-thread really matters
>>> any more.
>>>
>>> <cut stuff you ignored here bue have have discussed elsewhere>
>>>
>>
>> On 11/27/2020 9:02 PM, Ben Bacarisse wrote:
>>  > A computation that would not halt if its simulation were not
>>  > halted is indeed a non-halting computation.
>>
>> Just like there is no exception to this rule:
>> ∀n ∈ ℕ ((n > 5) → (N > 3))
>>
>> Every computation that would not halt unless its simulation was halted 
>> is by logical necessity a non-halting computation.
>>
>> Both the x86 virtual machine computation and its simulated Turing 
>> machine description equivalent computation would never halt unless 
>> their simulator stopped simulating them.
>>
>> In logic and mathematics, necessity and sufficiency are terms used to 
>> describe a conditional or implicational relationship between two 
>> statements. ... a sufficient condition is one which produces the said 
>> condition. https://en.wikipedia.org/wiki/Necessity_and_sufficiency
>>
>> When-so-ever
>> A computation would not halt unless its simulation was halted
>> this computation is necessarily always a non-halting computation.
>> THE SUFFICIENCY CONDITION IS FULLY MET !!!
>>
>> H_Hat <is> a computation that would not halt unless its simulation was 
>> halted ∴ (no matter how much you don't like it) H_Hat is a non-halting 
>> computation.
> 
> 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.

What I have done instead is show the exact steps required to decide the 
conventional halting problem proof counter examples of defining an input 
that does the opposite of whatever the halt decider decides:

Now we construct a new Turing machine D with H as a
subroutine. This new TM calls H to determine what M
does when the input to M is its own description <M>.
Once D has determined this information, it does the
opposite. That is, it rejects if M accepts and accepts
if M does not accept. The following is a description of D. (Sipser 1997)

D = "On input <M>, where M is a TM:
1. Run H on input <M, <M>>.
2. Output the opposite of what H outputs;
that is if H accepts, reject and if H rejects, accept."

http://www.liarparadox.org/sipser_165.pdf

Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: 
PWS Publishing Company (165-167)

> Publish your working code (complete solution) so we can see past the 
> guff and look at the actual implementation and then give it a test case 
> that it fails to analyse correctly.

My actual code is not ready for prime-time however the halt decider does 
provide the full execution trace that its decision is based on (every 
single assembly language instruction that was executed prior to 
terminating the simulation) and from this execution trace it can be 
verified that the decider did make the correct halt decision.

> Until you produce a working implementation in the form of code all you 
> have is conjecture; i.e. no refutation of the HP.
> 
> /Flibble
> 


-- 
Copyright 2020 Pete Olcott

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

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


#26229 — Re: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-11-30 21:06 +0000
SubjectRe: The key aspects of x86utm are now finally complete (Refuting the HP proofs)(keys to understanding)
Message-ID<20201130125512.705@kylheku.com>
In reply to#26222
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?

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-30 15:14 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<I5udnWySYf1e_VjCnZ2dnUU7-KmdnZ2d@giganews.com>
In reply to#26229
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.

Just like some people really believe that 250% of all of the beings in 
the universe voted for Trump some people deny infinite recursion even 
when it slaps them in the face.


-- 
Copyright 2020 Pete Olcott

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

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


#26237 — 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-11-30 22:48 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201130142819.218@kylheku.com>
In reply to#26231
["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.

The usual proofs just give a simple, direct representative of that class
for the sake of clarity, but it's obvious that an effective such program
can be written in an unlimited number of ways.

There is no way that a halting decider can distinguish whether the input
is one of the infinitely large class of H_Hat programs, or whether it an
innocent test case. That itself is a decision problem equivalent to
halting.

If you have make a halting-equivalent decision before deciding halting,
you've lost.

No level of simulation or execution trace monitoring, or any
number of nestings thereof, can fix this.

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.

Suppose that Halts includes some simple hacks in order to guess whether
some trivial infinite loop or recursion is happening inside P (evidence
that it's being gamed). Those simple hacks can be always be used to
create a test case which coaxes an incorrect result out of Halts.

The author of H_Hat procedure always has the last word. The proposed
halting function Halt exists first, and H_Hat is crafted afterward,
using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
instance from an infinite class of programs, not one specific program.

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-30 17:23 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<EfqdnV8AFZ1341jCnZ2dnUU7-XvNnZ2d@giganews.com>
In reply to#26237
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.


> The usual proofs just give a simple, direct representative of that class
> for the sake of clarity, but it's obvious that an effective such program
> can be written in an unlimited number of ways.
> 
> There is no way that a halting decider can distinguish whether the input
> is one of the infinitely large class of H_Hat programs, or whether it an
> innocent test case. That itself is a decision problem equivalent to
> halting.
> 
> If you have make a halting-equivalent decision before deciding halting,
> you've lost.

For the above H_Hat template it does not matter what state transitions 
comprise the unspecified (wildcard) state transitions: ⊢*

     H.q0 wMw ⊢* H.yes   if M applied to w halts, and
     H.q0 wMw ⊢* H.no    if M applied to w does not halt.

as long as the halt decider bases its decision on simulating its input 
then every single element of the class of H_Hat computations specifies 
infinite recursion.

> No level of simulation or execution trace monitoring, or any
> number of nestings thereof, can fix this.
> 
> 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?

> Suppose that Halts includes some simple hacks in order to guess whether
> some trivial infinite loop or recursion is happening inside P (evidence
> that it's being gamed). Those simple hacks can be always be used to
> create a test case which coaxes an incorrect result out of Halts.
> 
> The author of H_Hat procedure always has the last word. The proposed
> halting function Halt exists first, and H_Hat is crafted afterward,
> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
> instance from an infinite class of programs, not one specific program.
> 

The key thing that you are utterly oblivious to is that I just showed 
how to correctly decide the "impossible to decide" template of all the 
conventional "do the opposite of whatever the halt decider decides" 
halting problem counter-examples.

That is easy to miss when one starts with the fundamental goal:
How do I show Pete that he is wrong?

-- 
Copyright 2020 Pete Olcott

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

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


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

FromMr Flibble <flibbleREMOVETHISBIT@i42.co.uk>
Date2020-11-30 23:54 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<dDfxH.176510$b5kb.95272@fx15.ams4>
In reply to#26240
On 30/11/2020 23:23, olcott 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.
> 
> 
>> The usual proofs just give a simple, direct representative of that class
>> for the sake of clarity, but it's obvious that an effective such program
>> can be written in an unlimited number of ways.
>>
>> There is no way that a halting decider can distinguish whether the input
>> is one of the infinitely large class of H_Hat programs, or whether it an
>> innocent test case. That itself is a decision problem equivalent to
>> halting.
>>
>> If you have make a halting-equivalent decision before deciding halting,
>> you've lost.
> 
> For the above H_Hat template it does not matter what state transitions comprise the unspecified (wildcard) state transitions: ⊢*
> 
>      H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>      H.q0 wMw ⊢* H.no    if M applied to w does not halt.
> 
> as long as the halt decider bases its decision on simulating its input then every single element of the class of H_Hat computations specifies infinite recursion.
> 
>> No level of simulation or execution trace monitoring, or any
>> number of nestings thereof, can fix this.
>>
>> 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?
> 
>> Suppose that Halts includes some simple hacks in order to guess whether
>> some trivial infinite loop or recursion is happening inside P (evidence
>> that it's being gamed). Those simple hacks can be always be used to
>> create a test case which coaxes an incorrect result out of Halts.
>>
>> The author of H_Hat procedure always has the last word. The proposed
>> halting function Halt exists first, and H_Hat is crafted afterward,
>> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
>> instance from an infinite class of programs, not one specific program.
>>
> 
> The key thing that you are utterly oblivious to is that I just showed how to correctly decide the "impossible to decide" template of all the conventional "do the opposite of whatever the halt decider decides" halting problem counter-examples.
> 
> That is easy to miss when one starts with the fundamental goal:
> How do I show Pete that he is wrong?

Your wrongness is fractal in nature.  Deliver an open source working implementation that backs up your claims or fuck off, spammer.

/Flibble

-- 
¬

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-30 18:08 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<FZ6dnTSyifT-FFjCnZ2dnUU7-fnNnZ2d@giganews.com>
In reply to#26242
On 11/30/2020 5:54 PM, Mr Flibble wrote:
> On 30/11/2020 23:23, olcott 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.
>>
>>
>>> The usual proofs just give a simple, direct representative of that class
>>> for the sake of clarity, but it's obvious that an effective such program
>>> can be written in an unlimited number of ways.
>>>
>>> There is no way that a halting decider can distinguish whether the input
>>> is one of the infinitely large class of H_Hat programs, or whether it an
>>> innocent test case. That itself is a decision problem equivalent to
>>> halting.
>>>
>>> If you have make a halting-equivalent decision before deciding halting,
>>> you've lost.
>>
>> For the above H_Hat template it does not matter what state transitions 
>> comprise the unspecified (wildcard) state transitions: ⊢*
>>
>>      H.q0 wMw ⊢* H.yes   if M applied to w halts, and
>>      H.q0 wMw ⊢* H.no    if M applied to w does not halt.
>>
>> as long as the halt decider bases its decision on simulating its input 
>> then every single element of the class of H_Hat computations specifies 
>> infinite recursion.
>>
>>> No level of simulation or execution trace monitoring, or any
>>> number of nestings thereof, can fix this.
>>>
>>> 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?
>>
>>> Suppose that Halts includes some simple hacks in order to guess whether
>>> some trivial infinite loop or recursion is happening inside P (evidence
>>> that it's being gamed). Those simple hacks can be always be used to
>>> create a test case which coaxes an incorrect result out of Halts.
>>>
>>> The author of H_Hat procedure always has the last word. The proposed
>>> halting function Halt exists first, and H_Hat is crafted afterward,
>>> using full knowledge of Halt. Moreover, as noted, H_Hat is actually an
>>> instance from an infinite class of programs, not one specific program.
>>>
>>
>> The key thing that you are utterly oblivious to is that I just showed 
>> how to correctly decide the "impossible to decide" template of all the 
>> conventional "do the opposite of whatever the halt decider decides" 
>> halting problem counter-examples.
>>
>> That is easy to miss when one starts with the fundamental goal:
>> How do I show Pete that he is wrong?
> 
> Your wrongness is fractal in nature.  Deliver an open source working 
> implementation that backs up your claims or fuck off, spammer.
> 
> /Flibble
> 

If you can't verify what I said on the basis the infinite recursion that 
I just proved, you won't be able to understand the source code either.


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

for the whole class of computations specified by the above template

 >>>> Halts((u32)H_Hat, (u32)H_Hat) specifies infinite recursion
 >>>> thus can be decided as non halting.


-- 
Copyright 2020 Pete Olcott

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

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


Page 3 of 5 — ← Prev page 1 2 [3] 4 5  Next page →

Back to top | Article view | comp.theory


csiph-web