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 4 of 5 — ← Prev page 1 2 3 [4] 5  Next page →


#26244 — 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:18 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<odOdnRng2b18FljCnZ2dnUU7-I3NnZ2d@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
> 

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

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

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

 From the above infinite recursion it is easy to see that when 
DebugTrace(P, P) is replaced with a full x86 emulator that we still have 
infinite recursion.

This logically entails that any halt decider based on an x86 emulator 
would be also infinitely recursive too. (such as the first H_Hat above).

This logically entails that we can correctly decide not halting on the 
whole class of computations specified by the origibal H_Hat above, as 
long as the halt decider is based on x86 emulation.

This logically entails that we can decide not halting on the equivalent 
computation where an actual Turing machine partial halt decider bases 
its decision on simulating its input Turing machine description.

-- 
Copyright 2020 Pete Olcott

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

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


#26245 — 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:59 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<I9udnSLXI9rpCFjCnZ2dnUU7-e3NnZ2d@giganews.com>
In reply to#26244
On 11/30/2020 6:18 PM, olcott wrote:
> 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
>>
> 
> int DebugTrace(u32 P, u32 I)
> {
>    ((int(*)(int))P)(I);
>    return 1;
> }
> 
> void H_Hat(u32 P)
> {
>    u32 Aborted = DebugTrace(P, P);
>    if (Aborted)
>      HALT
>    else
>      HERE: goto HERE;
> }
> 
> int main()
> {
>    u32 P = (u32)H_Hat;
>    DebugTrace(P, P);
>    HALT;
> }
> 
>  From the above infinite recursion it is easy to see that when 
> DebugTrace(P, P) is replaced with a full x86 emulator that we still have 
> infinite recursion.
> 
> This logically entails that any halt decider based on an x86 emulator 
> would be also infinitely recursive too. (such as the first H_Hat above).
> 
> This logically entails that we can correctly decide not halting on the 
> whole class of computations specified by the origibal H_Hat above, as 
> long as the halt decider is based on x86 emulation.
> 
> This logically entails that we can decide not halting on the equivalent 
> computation where an actual Turing machine partial halt decider bases 
> its decision on simulating its input Turing machine description.
> 

This last part may be a little more difficult to see because textbooks 
probably never delve into the case where a UTM is simulating its own 
Turing Machine Description simulating this same Turing Machine 
Description. It may not be clear that this is the TM equivalent of 
recursive invocation:

UTM1(<TM1>, DATA) ≡ TM1(DATA)
∴
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]


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

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 01:40 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201130172804.625@kylheku.com>
In reply to#26244
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> int DebugTrace(u32 P, u32 I)
> {
>    ((int(*)(int))P)(I);
>    return 1;
> }
>
> void H_Hat(u32 P)
> {
>    u32 Aborted = DebugTrace(P, P);
>    if (Aborted)
>      HALT
>    else
>      HERE: goto HERE;
> }
>
> int main()
> {
>    u32 P = (u32)H_Hat;
>    DebugTrace(P, P);
>    HALT;
> }
>
>  From the above infinite recursion it is easy to see that when 
> DebugTrace(P, P) is replaced with a full x86 emulator that we still have 
> infinite recursion.

In that case we must detect the recursion and report that the program
does not halt; we can't just let it go on. This means that we are
looking for a specific pattern of execution which looks like runaway
recursion.

Problem is, H_Hat can be this (among other possible structures in a
similar vain):

 void H_Hat(u32 P)
 {
    Decoy_1003(P); // One of an infinite library of decoys

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

Some of the decoys terminate, and so the DebugTrace line is
executed. Some do not terminate.

The manners in which the non-terminating ones fail to terminate is
completely arbitrary; it doesn't necessarily look anything like the
infinite recursion execution trace pattern.

Stepping through a program to decide its halting is completely
wrongheaded. We cannot decide halting that way. If we actually
execute a program P on input I, it either halts (whereupon halting
is decided) or does not, in which case halting remains undecided.

To decide halting means to calculate, in a finite number of steps,
whether any P on any I halts or does not halt.

Allowing P to execute, and monitoring it for specific non-termination
patterns does not add up to a halting decider.

The problem is that as you execute P(I), looking for it to hit
one of the specific non-terminating patterns, it might appear not
to be hitting any of those patterns---and yet not terminating!

Your only choices are:

1) step yet anoher instruction cycle and hope that one of the
non-termination patterns (such as a specific instance of runaway
recursion) appears, so you can conclude "does not terminate".

2) give up.

But (2) means you must report "undecided": you have failed to
decide whether P halts on I.

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-11-30 19:48 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<T_qdnVVBhKNOPVjCnZ2dnUU7-I3NnZ2d@giganews.com>
In reply to#26250
On 11/30/2020 7:40 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> int DebugTrace(u32 P, u32 I)
>> {
>>     ((int(*)(int))P)(I);
>>     return 1;
>> }
>>
>> void H_Hat(u32 P)
>> {
>>     u32 Aborted = DebugTrace(P, P);
>>     if (Aborted)
>>       HALT
>>     else
>>       HERE: goto HERE;
>> }
>>
>> int main()
>> {
>>     u32 P = (u32)H_Hat;
>>     DebugTrace(P, P);
>>     HALT;
>> }
>>
>>   From the above infinite recursion it is easy to see that when
>> DebugTrace(P, P) is replaced with a full x86 emulator that we still have
>> infinite recursion.
> 
> In that case we must detect the recursion and report that the program
> does not halt; we can't just let it go on. This means that we are
> looking for a specific pattern of execution which looks like runaway
> recursion.
> 
> Problem is, H_Hat can be this (among other possible structures in a
> similar vain):

The key is that whenever Halts is based on emulation that every instance 
of the template of H_Hat shown above <is> infinitely recursive.

I skimmed what you said below and it is all beside the point that I just 
made. The H_Hat template <is> the template of every conventional halting 
problem proof, thus deciding this one template refutes all these proofs.

>   void H_Hat(u32 P)
>   {
>      Decoy_1003(P); // One of an infinite library of decoys
> 
>      u32 Aborted = DebugTrace(P, P);
>      if (Aborted)
>        HALT
>      else
>        HERE: goto HERE;
>   }
> 
> Some of the decoys terminate, and so the DebugTrace line is
> executed. Some do not terminate.
> 
> The manners in which the non-terminating ones fail to terminate is
> completely arbitrary; it doesn't necessarily look anything like the
> infinite recursion execution trace pattern.
> 
> Stepping through a program to decide its halting is completely
> wrongheaded. We cannot decide halting that way. If we actually
> execute a program P on input I, it either halts (whereupon halting
> is decided) or does not, in which case halting remains undecided.
> 
> To decide halting means to calculate, in a finite number of steps,
> whether any P on any I halts or does not halt.
> 
> Allowing P to execute, and monitoring it for specific non-termination
> patterns does not add up to a halting decider.
> 
> The problem is that as you execute P(I), looking for it to hit
> one of the specific non-terminating patterns, it might appear not
> to be hitting any of those patterns---and yet not terminating!
> 
> Your only choices are:
> 
> 1) step yet anoher instruction cycle and hope that one of the
> non-termination patterns (such as a specific instance of runaway
> recursion) appears, so you can conclude "does not terminate".
> 
> 2) give up.
> 
> But (2) means you must report "undecided": you have failed to
> decide whether P halts on I.
> 


-- 
Copyright 2020 Pete Olcott

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

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


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

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 08:41 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201201002056.333@kylheku.com>
In reply to#26252
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> I skimmed what you said below and it is all beside the point that I just
> made.

Here we go: this is how you dismiss situations that reveal flaws in your
so-called work, and then continue to claim that no flaws have been found.

> The H_Hat template <is> the template of every conventional halting
> problem proof, thus deciding this one template refutes all these proofs.

In other words, you're attacking a strawman version of the proof,
by taking a particular pseudo-code template literally.

You're not taking on the general technique given in the proof.

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


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

FromMalcolm McLean <malcolm.arthur.mclean@gmail.com>
Date2020-12-01 04:00 -0800
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<e161940d-3bc0-4a6f-ad86-45679e7854d7n@googlegroups.com>
In reply to#26260
On Tuesday, 1 December 2020 at 08:42:01 UTC, Kaz Kylheku wrote:
> On 2020-12-01, olcott <No...@NoWhere.com> wrote: 
> > I skimmed what you said below and it is all beside the point that I just 
> > made.
> Here we go: this is how you dismiss situations that reveal flaws in your 
> so-called work, and then continue to claim that no flaws have been found.
> > The H_Hat template <is> the template of every conventional halting 
> > problem proof, thus deciding this one template refutes all these proofs.
> In other words, you're attacking a strawman version of the proof, 
> by taking a particular pseudo-code template literally. 
> 
> You're not taking on the general technique given in the proof.
>
No, that's reasonable. If he can produc a pair of Turing machines,
one of which is a "partial halt decider", the other which calls that
decider and inverts the result, and somehow gets consistent results
on the call to the decider and the direct run, then he's refuted the proof.

The halt decider doesn't have to handle every case, and it doesn't have to
work for the infinite possible variations on the H_Hat theme. You just
need one counter-example and the proof falls.

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 09:13 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<haCdnVzdRb8lwFvCnZ2dnUU7-L-dnZ2d@giganews.com>
In reply to#26263
On 12/1/2020 6:00 AM, Malcolm McLean wrote:
> On Tuesday, 1 December 2020 at 08:42:01 UTC, Kaz Kylheku wrote:
>> On 2020-12-01, olcott <No...@NoWhere.com> wrote:
>>> I skimmed what you said below and it is all beside the point that I just
>>> made.
>> Here we go: this is how you dismiss situations that reveal flaws in your
>> so-called work, and then continue to claim that no flaws have been found.
>>> The H_Hat template <is> the template of every conventional halting
>>> problem proof, thus deciding this one template refutes all these proofs.
>> In other words, you're attacking a strawman version of the proof,
>> by taking a particular pseudo-code template literally.
>>
>> You're not taking on the general technique given in the proof.
>>
> No, that's reasonable. If he can produc a pair of Turing machines,
> one of which is a "partial halt decider", the other which calls that
> decider and inverts the result, and somehow gets consistent results
> on the call to the decider and the direct run, then he's refuted the proof.
> 
> The halt decider doesn't have to handle every case, and it doesn't have to
> work for the infinite possible variations on the H_Hat theme. You just
> need one counter-example and the proof falls.
> 

Bingo !!!   Thanks for your support !!!

-- 
Copyright 2020 Pete Olcott

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

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


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

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 17:32 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201201091621.263@kylheku.com>
In reply to#26263
On 2020-12-01, Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> On Tuesday, 1 December 2020 at 08:42:01 UTC, Kaz Kylheku wrote:
>> On 2020-12-01, olcott <No...@NoWhere.com> wrote: 
>> > I skimmed what you said below and it is all beside the point that I just 
>> > made.
>> Here we go: this is how you dismiss situations that reveal flaws in your 
>> so-called work, and then continue to claim that no flaws have been found.
>> > The H_Hat template <is> the template of every conventional halting 
>> > problem proof, thus deciding this one template refutes all these proofs.
>> In other words, you're attacking a strawman version of the proof, 
>> by taking a particular pseudo-code template literally. 
>> 
>> You're not taking on the general technique given in the proof.
>>
> No, that's reasonable. If he can produc a pair of Turing machines,
> one of which is a "partial halt decider", the other which calls that
> decider and inverts the result, and somehow gets consistent results
> on the call to the decider and the direct run, then he's refuted the proof.

Olcott is working against strawman versions of the proof which use
hand-waving arguments and pseudo-code in order to be easy to follow.

He's retaining their basic syntax, and changing he computational
semantics underneath to include bizarre concoctions involving x86
emulators and single-step debuggers and whatnot.

This is highly suspect. Maybe those simplified proofs hold up
under those conditions, maybe not. In any case, I show that
we can easily modify the programs to foil the decider; if there is a
flaw in the proofs, it can trivially be repaired.

Turing rigorously performed his work using the concrete Turing machines,
in which every mechanism of action is specified in detail.

A program P and its input I, are all specified via encoding to the
the initial state of a tape.

That's what you have to work with if you want to refute anything.

There are no "calls" from one machine to another.

There is no "pair of Turing machines". The halting decider is a single
Turing machine, which has been initialized with some combination of the
halt-deciding instructions, the program P and its input I.  These are
encoded on the tape, and then the machine takes it from there.

If it happens that P does not halt on input I, nevertheless the halting
decider must announce that fact, in a finite number of steps; it must
not itself fail to halt. (Therefore, simply simulating the action of P
and I, and checking for termination, equivalent to executing P(I) and
seeing what happens, will not produce a decider.)

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


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

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

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

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

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

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

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


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


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

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


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



-- 
Copyright 2020 Pete Olcott

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

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


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

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

[ snip ]

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

> The PRIOR Instruction Specifies Infinite Recursion: Simulation Stopped:

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

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

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

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

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

- Has it decided that H_Hat(H_Hat) halts?

- Or has it decided that it does not halt?

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

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

  void H_Hat(u32 P)
  {
    HALT;
  }

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

and:

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

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

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


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

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


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

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

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

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

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

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

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

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

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

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

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

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


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


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


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

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


-- 
Copyright 2020 Pete Olcott

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

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 08:52 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<ftqdnT2Vt805xVvCnZ2dnUU7-bfNnZ2d@giganews.com>
In reply to#26260
On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> I skimmed what you said below and it is all beside the point that I just
>> made.
> 
> Here we go: this is how you dismiss situations that reveal flaws in your
> so-called work, and then continue to claim that no flaws have been found.
> 
>> The H_Hat template <is> the template of every conventional halting
>> problem proof, thus deciding this one template refutes all these proofs.
> 
> In other words, you're attacking a strawman version of the proof,
> by taking a particular pseudo-code template literally.
> 
> You're not taking on the general technique given in the proof.
> 

If you try and provide the reasoning supporting this empty assertion you 
will find that there is none.

This is computationally equivalent to every conventional halting problem 
counter-example that "does the opposite of whatever the halt decide 
decides":

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


You can claim that it is not equivalent the same way that you can claim 
that there are 10,000 fairies dancing on the head of every pin.

x86 language ≡ von Neumann architecture ≡ UTM ≡ RASP Machine

What you cannot do is show that I am incorrect. We are at the point 
where no one has even slightly plausible rebuttals.

-- 
Copyright 2020 Pete Olcott

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

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


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

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

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

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

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

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


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

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

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

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

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 15:49 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<Rs6dnQj9i_XnJ1vCnZ2dnUU7-ImdnZ2d@giganews.com>
In reply to#26279
On 12/1/2020 3:30 PM, Kaz Kylheku wrote:
> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>> On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
>> This is computationally equivalent to every conventional halting problem
>> counter-example that "does the opposite of whatever the halt decide
>> decides":
>>
>> void H_Hat(u32 P)
>> {
>>     u32 Input_Halts = Halts(P, P);
>>     if (!Input_Halts)
>>       HALT
>>     else
>>       HERE: goto HERE;
>> }
> 
> This is just an element of the "educational" version of the proof.
> 
> It's obvious to everyone that strawman interpretations of this have
> weaknesses; if it were compiled on an actual machine, there will be
> instruction sequences that a VM could look for to detect the trivial
> loop and such.
> 
> You must make the strongest possible interpretation of this.
> For instance, H_Hat can invoke Halts using a tamper-proof virtual
> machine of its own.

I only have to find one case of the conventional halting problem proof 
"do the opposite of whatever the halt decider decides" to refute all of 
these proofs.

Malcolm understands this:

On 12/1/2020 6:00 AM, Malcolm McLean wrote:
 > No, that's reasonable. If he can produc a pair of Turing machines,
 > one of which is a "partial halt decider", the other which calls that
 > decider and inverts the result, and somehow gets consistent results
 > on the call to the decider and the direct run, then he's refuted
 > the proof.
 >
 > The halt decider doesn't have to handle every case, and it
 > doesn't have to
 > work for the infinite possible variations on the H_Hat theme. You just
 > need one counter-example and the proof falls.
 >

I DO NOT HAVE TO SOLVE THE HALTING PROBLEM TO REFUTE THE CONVENTIONAL 
PROOFS.

> Or: I can write H_Hat in a custom programming language, which compiles
> to byte code. And then H_Hat looks like this:
> 
> 
>     uint8_t H_Hat_Bytecode = { 0xF3, 0xD9, ... reams of hex };
> 
>     void H_Hat(P)
>     {
>        H_Hat_Bytecode_Execute(H_Hat_Bytecode, P);
>     }
> 
> now the "HERE: goto HERE" is hidden in bytecode. A completely different
> strategy is needed to discover it, since it is not apparent in any
> native instruction sequence.
> 


-- 
Copyright 2020 Pete Olcott

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

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


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

FromKaz Kylheku <563-365-8930@kylheku.com>
Date2020-12-01 22:22 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<20201201141130.178@kylheku.com>
In reply to#26281
On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
> On 12/1/2020 3:30 PM, Kaz Kylheku wrote:
>> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>>> On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
>>> This is computationally equivalent to every conventional halting problem
>>> counter-example that "does the opposite of whatever the halt decide
>>> decides":
>>>
>>> void H_Hat(u32 P)
>>> {
>>>     u32 Input_Halts = Halts(P, P);
>>>     if (!Input_Halts)
>>>       HALT
>>>     else
>>>       HERE: goto HERE;
>>> }
>> 
>> This is just an element of the "educational" version of the proof.
>> 
>> It's obvious to everyone that strawman interpretations of this have
>> weaknesses; if it were compiled on an actual machine, there will be
>> instruction sequences that a VM could look for to detect the trivial
>> loop and such.
>> 
>> You must make the strongest possible interpretation of this.
>> For instance, H_Hat can invoke Halts using a tamper-proof virtual
>> machine of its own.
>
> I only have to find one case of the conventional halting problem proof 
> "do the opposite of whatever the halt decider decides" to refute all of 
> these proofs.

You're only refuting a strawman interpretation of proof sketches.

Those proof skeches are for educational purposes; they are not the
intellectual work that underlies our understanding of computability.

>> Or: I can write H_Hat in a custom programming language, which compiles
>> to byte code. And then H_Hat looks like this:
>> 
>> 
>>     uint8_t H_Hat_Bytecode = { 0xF3, 0xD9, ... reams of hex };
>> 
>>     void H_Hat(P)
>>     {
>>        H_Hat_Bytecode_Execute(H_Hat_Bytecode, P);
>>     }

The above is still the "conventional template"; I just compiled
it a particular way.

That is to say, I can have a program which /automatically/ converts this:

     void H_Hat(P)
     {
        if (Halts(P, P))
        {
            for (;;);
        }
        else
        {
            HALT;
        }
     }

into custom byte code:

    void H_Hat(P)
    {
       static uint8_t bytecode = { 0xF3, 0xD9, ... };
       bytecode_execute(bytecode, P);
    }

I'm still conforming to the template.

The popular proof sketches of the halting problem do not say that the
template may not be translated into another representation by a
compiler.

Doing exactly that is what your own argumentation is depending on.

I'm saying that the H_Hat author gets first dibs at the code and gets to
translate the whole thing into something else, as long as it can still
somehow execute your Halts routine.

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


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

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

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

-- 
Copyright 2020 Pete Olcott

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

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


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

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

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

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

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

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

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


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

FromRichard Damon <Richard@Damon-Family.org>
Date2020-12-01 21:51 -0500
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<RiDxH.82562$Uz.42269@fx46.iad>
In reply to#26281
On 12/1/20 4:49 PM, olcott wrote:
> On 12/1/2020 3:30 PM, Kaz Kylheku wrote:
>> On 2020-12-01, olcott <NoOne@NoWhere.com> wrote:
>>> On 12/1/2020 2:41 AM, Kaz Kylheku wrote:
>>> This is computationally equivalent to every conventional halting problem
>>> counter-example that "does the opposite of whatever the halt decide
>>> decides":
>>>
>>> void H_Hat(u32 P)
>>> {
>>>     u32 Input_Halts = Halts(P, P);
>>>     if (!Input_Halts)
>>>       HALT
>>>     else
>>>       HERE: goto HERE;
>>> }
>>
>> This is just an element of the "educational" version of the proof.
>>
>> It's obvious to everyone that strawman interpretations of this have
>> weaknesses; if it were compiled on an actual machine, there will be
>> instruction sequences that a VM could look for to detect the trivial
>> loop and such.
>>
>> You must make the strongest possible interpretation of this.
>> For instance, H_Hat can invoke Halts using a tamper-proof virtual
>> machine of its own.
> 
> I only have to find one case of the conventional halting problem proof
> "do the opposite of whatever the halt decider decides" to refute all of
> these proofs.
> 
> Malcolm understands this:
> 
> On 12/1/2020 6:00 AM, Malcolm McLean wrote:
>> No, that's reasonable. If he can produc a pair of Turing machines,
>> one of which is a "partial halt decider", the other which calls that
>> decider and inverts the result, and somehow gets consistent results
>> on the call to the decider and the direct run, then he's refuted
>> the proof.
>>
>> The halt decider doesn't have to handle every case, and it
>> doesn't have to
>> work for the infinite possible variations on the H_Hat theme. You just
>> need one counter-example and the proof falls.
>>
> 
> I DO NOT HAVE TO SOLVE THE HALTING PROBLEM TO REFUTE THE CONVENTIONAL
> PROOFS.
> 

But Halts above is NOT the counter example, because Halts is NOT the
Halt decider of Linz, as it does not return the answer.

To make it the PROPER Linz rebuttal, you need to replace the Halts above
with H, a function built by taking your actual Halt Decider (your WHOLE
OS it sounds), and returning the decision. And when we do this, you
counter proof falls flat.

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


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

FromAndy Walker <anw@cuboid.co.uk>
Date2020-12-01 15:22 +0000
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<rq5n3n$r7g$1@gioia.aioe.org>
In reply to#26250
On 01/12/2020 01:40, Kaz Kylheku wrote:
> Stepping through a program to decide its halting is completely
> wrongheaded.

	It's not /completely/ wrong-headed. ...

>	       We cannot decide halting that way. If we actually
> execute a program P on input I, it either halts (whereupon halting
> is decided) or does not, in which case halting remains undecided.
[...]
> Your only choices are:
> 1) step yet anoher instruction cycle and hope that one of the
> non-termination patterns (such as a specific instance of runaway
> recursion) appears, so you can conclude "does not terminate".
> 2) give up.

	... The set of P and I of a given size [measured in some
reasonable way, such as the number of bytes needed to define P and
to list I] is finite, and "easily" enumerated.  For a given P,I,
define N_P,I to be 0 if P doesn't halt on I, and otherwise to be
the number of steps taken by P before halting.  Let S be the max
over that set of P,I of N_P,I.  Then an emulation of P on I for
S steps shows either that P on I halts or that it will never
halt.  But, you object, we need to know whether P on I halts
before we can calculate S.  True, I riposte, but we don't need
to know S exactly, any bound /whatsoever/ on S will suffice.

	Now the argument can go either of two ways.  (a) Since
the HP is "unsolvable", this shows that S is uncomputable, even
though it's just any sufficiently large, and otherwise perfectly
unexceptional, integer.  Or (b), by an argument very similar to
Busy Beaver theory, we can show directly that S is uncomputable
and deduce that the HP is "unsolvable".  [This proof is independent
of the "Linz H_hat" argument that PO so dislikes, and also of the
two-liner that Linz prefers, as given also by Mr Flibble.]

	IOW, emulation is doomed to failure, but not in such an
obvious way that it's wrong-headed, which I would reserve for
approaches to problems that anyone should be able to see in
advance are not going to work.

	[I put "unsolvable" in quotes as shorthand for "there is
no Turing machine or near equivalent that solves the general
problem", as any fule kno.*]

____
   * https://en.wikipedia.org/wiki/Nigel_Molesworth

-- 
Andy Walker, Nottingham.
    Andy's music pages: www.cuboid.me.uk/andy/Music
    Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Kontski

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


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

Fromolcott <NoOne@NoWhere.com>
Date2020-12-01 09:33 -0600
SubjectRe: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Message-ID<UvCdne0FaPn5_1vCnZ2dnUU7-bfNnZ2d@giganews.com>
In reply to#26267
On 12/1/2020 9:22 AM, Andy Walker wrote:
> On 01/12/2020 01:40, Kaz Kylheku wrote:
>> Stepping through a program to decide its halting is completely
>> wrongheaded.
> 
>      It's not /completely/ wrong-headed. ...
> 
>>            We cannot decide halting that way. If we actually
>> execute a program P on input I, it either halts (whereupon halting
>> is decided) or does not, in which case halting remains undecided.
> [...]
>> Your only choices are:
>> 1) step yet anoher instruction cycle and hope that one of the
>> non-termination patterns (such as a specific instance of runaway
>> recursion) appears, so you can conclude "does not terminate".
>> 2) give up.
> 
>      ... The set of P and I of a given size [measured in some
> reasonable way, such as the number of bytes needed to define P and
> to list I] is finite, and "easily" enumerated.  For a given P,I,
> define N_P,I to be 0 if P doesn't halt on I, and otherwise to be
> the number of steps taken by P before halting.  Let S be the max
> over that set of P,I of N_P,I.  Then an emulation of P on I for
> S steps shows either that P on I halts or that it will never
> halt.  But, you object, we need to know whether P on I halts
> before we can calculate S.  True, I riposte, but we don't need
> to know S exactly, any bound /whatsoever/ on S will suffice.
> 
>      Now the argument can go either of two ways.  (a) Since
> the HP is "unsolvable", this shows that S is uncomputable, even
> though it's just any sufficiently large, and otherwise perfectly
> unexceptional, integer.  Or (b), by an argument very similar to
> Busy Beaver theory, we can show directly that S is uncomputable
> and deduce that the HP is "unsolvable".  [This proof is independent
> of the "Linz H_hat" argument that PO so dislikes, and also of the
> two-liner that Linz prefers, as given also by Mr Flibble.]
> 
>      IOW, emulation is doomed to failure, but not in such an
> obvious way that it's wrong-headed, which I would reserve for
> approaches to problems that anyone should be able to see in
> advance are not going to work.
> 
>      [I put "unsolvable" in quotes as shorthand for "there is
> no Turing machine or near equivalent that solves the general
> problem", as any fule kno.*]
> 
> ____
>    * https://en.wikipedia.org/wiki/Nigel_Molesworth
> 

Here is another choice from fully operational code.

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

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


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


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

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


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

-- 
Copyright 2020 Pete Olcott

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

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


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

Back to top | Article view | comp.theory


csiph-web