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


Groups > comp.software-eng > #2017

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

From Kaz Kylheku <563-365-8930@kylheku.com>
Newsgroups comp.theory, comp.ai.philosophy, comp.software-eng
Subject Re: The key aspects of x86utm are now finally complete (infinite recursion slaps them in the face)
Followup-To comp.theory
Date 2020-12-01 18:35 +0000
Organization Aioe.org NNTP Server
Message-ID <20201201101804.411@kylheku.com> (permalink)
References (18 earlier) <T_qdnVVBhKNOPVjCnZ2dnUU7-I3NnZ2d@giganews.com> <20201201002056.333@kylheku.com> <e161940d-3bc0-4a6f-ad86-45679e7854d7n@googlegroups.com> <20201201091621.263@kylheku.com> <lvSdnVrkbdISGlvCnZ2dnUU7-fvNnZ2d@giganews.com>

Cross-posted to 3 groups.

Followups directed to: comp.theory

Show all headers | View raw


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

Back to comp.software-eng | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

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

csiph-web