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


Groups > comp.lang.c > #159113

Re: Detecting infinite recursion (H_Hat is proved to be decidable)

From Kaz Kylheku <563-365-8930@kylheku.com>
Newsgroups comp.lang.c, comp.theory
Subject Re: Detecting infinite recursion (H_Hat is proved to be decidable)
Followup-To comp.lang.c
Date 2021-03-01 16:52 +0000
Organization A noiseless patient Spider
Message-ID <20210301084705.697@kylheku.com> (permalink)
References (16 earlier) <gvSdnVGYXLmIW6b9nZ2dnUU7-dvNnZ2d@giganews.com> <mhQ_H.83465$w0C2.72737@fx02.ams4> <vsWdnaqGeKOtd6b9nZ2dnUU7-W3NnZ2d@giganews.com> <20210228194941.651@kylheku.com> <RL-dna39uu3f9qH9nZ2dnUU78fXNnZ2d@giganews.com>

Cross-posted to 2 groups.

Followups directed to: comp.lang.c

Show all headers | View raw


["Followup-To:" header set to comp.lang.c.]
On 2021-03-01, olcott <NoOne@NoWhere.com> wrote:
> On 2/28/2021 9:52 PM, Kaz Kylheku wrote:
>> On 2021-02-28, olcott <NoOne@NoWhere.com> wrote:
>>> This instance of H_Hat() is proved to be decidable and all the code is
>>> provided. This H_Hat() calls Simulate() that returns true whenever its
>>> input halts.
>> 
>> Your eyes keep slipping off the carrot every once in a short while.
>> 
>> What's not decidable is universal halting, not any one specific program
>> and its input.
>> 
>> Any method by which you can decide a specific program and its input will
>> also work for some other programs/inputs, but not all of them.
>> 
>
> Hi Kaz:
>
> // P has the machine address of H_Hat()
> void H_Hat(u32 P)
> {
>    u32 Input_Halts = Simulate(P, P);
>    if (Input_Halts)
>      HERE: goto HERE;
>    return;
> }
>
> I am proceeding with my analysis with the smallest possible increments 
> of elaboration.
>
> The current point in the elaboration path that I am building a consensus 
> on now is that the above code can be decided to be necessarily 
> infinitely recursive if:

Since the code runs on a finite state machine, it cannot be infinitely
recursive. the finite approximation of infinitely recursive,
namely "runaway recursive": it proceeds in a process that resembles
infinite recursion, until it hits a resource limit.

While that might seem like picking nits, in the context of working
toward some result in the computability, it isn't.

> (1) We show that its x86 execute trace calls Simulate two times in 
> sequence with the same data. (Richard Damon came up with this 
> simplification and Mike Terry seems to concur.)
>
> (2) Simulate() only emulates the x86 machine code of H_Hat() and nothing 
> mode.

You're missing important conditions here.

The function H_Hat does not mention itself anywhere, so it is not
inherently recursive at all.  If the parameter P points to H_Hat, then
there is recursion.

The recursion is obviously runaway recursion, but only if another
condition is met, which is that Simulate(P, P) is a correct
and sufficiently complete implementation of the instruction set
in which P is written.

If Simulate plays Pac Man on the screen instead of simulating P,
then we don't have runaway recursion.

If Simulate decides to quit after doing 5000 instruction, long before
any resource limit is encountered, then we don't have runaway recursion.

-- 
TXR Programming Language: http://nongnu.org/txr
Cygna: Cygwin Native Application Library: http://kylheku.com/cygnal

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


Thread

Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-26 13:53 -0600
  Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-02-26 12:48 -0800
  Re: Detecting infinite recursion Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-02-26 21:37 +0000
    Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-02-26 15:26 -0800
  Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-02-27 01:58 +0000
  Re: Detecting infinite recursion Jeff Barnett <jbb@notatt.com> - 2021-02-26 21:32 -0700
  Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-02-28 13:08 -0600
    Re: Detecting infinite recursion (H_Hat is proved to be decidable) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-01 03:52 +0000
      Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-02-28 22:19 -0600
        Re: Detecting infinite recursion (H_Hat is proved to be decidable) Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2021-03-01 02:06 -0800
          Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 08:24 -0600
            Re: Detecting infinite recursion (H_Hat is proved to be decidable) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-01 17:06 +0000
              Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 11:47 -0600
        Re: Detecting infinite recursion (H_Hat is proved to be decidable) Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-03-01 13:10 +0000
          Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 08:30 -0600
        Re: Detecting infinite recursion (H_Hat is proved to be decidable) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-01 16:52 +0000
          Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 11:26 -0600
          Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 11:30 -0600
            Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-01 21:32 -0600
            Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-02 09:29 -0600
  Re: Detecting infinite recursion om@iki.fi (Otto J. Makela) - 2021-03-02 18:36 +0200
    Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 11:22 -0600
      Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 17:46 +0000
        Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 13:00 -0600
          Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 19:35 +0000
            Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 14:02 -0600
          Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 13:50 -0600
            Re: Detecting infinite recursion Kaz Kylheku <563-365-8930@kylheku.com> - 2021-03-02 19:57 +0000
              Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 14:20 -0600
              Re: Detecting infinite recursion Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-03-02 12:57 -0800
                Re: Detecting infinite recursion gazelle@shell.xmission.com (Kenny McCormack) - 2021-03-03 02:17 +0000
      Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-03-02 11:45 -0800
        Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 13:52 -0600
          Re: Detecting infinite recursion Siri Cruise <chine.bleu@yahoo.com> - 2021-03-02 12:04 -0800
            Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-02 14:49 -0600
          Re: Detecting infinite recursion Richard Damon <Richard@Damon-Family.org> - 2021-03-02 15:52 -0500
            Re: Detecting infinite recursion is simple olcott <NoOne@NoWhere.com> - 2021-03-02 15:08 -0600
              Re: Detecting infinite recursion is simple Richard Damon <Richard@Damon-Family.org> - 2021-03-02 17:33 -0500
                Re: Detecting infinite recursion is simple olcott <NoOne@NoWhere.com> - 2021-03-02 17:18 -0600
          Re: Detecting infinite recursion (credit where it is due) olcott <NoOne@NoWhere.com> - 2021-03-02 18:45 -0600
    Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-03 12:52 -0600
    Re: Detecting infinite recursion (rewritten) olcott <NoOne@NoWhere.com> - 2021-03-03 17:06 -0600
  Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-03-03 12:55 -0600
  Re: Detecting infinite recursion (halt deciding criteria) olcott <NoOne@NoWhere.com> - 2021-03-03 15:50 -0600
  Re: Detecting infinite recursion Bonita Montero <Bonita.Montero@gmail.com> - 2021-03-04 13:09 +0100
  Re: Detecting infinite recursion (pathological self-reference error) olcott <NoOne@NoWhere.com> - 2021-03-06 09:58 -0600
  Re: Detecting infinite recursion Bonita Montero <Bonita.Montero@gmail.com> - 2021-03-07 16:38 +0100
    Re: Detecting infinite recursion (halting problem) olcott <NoOne@NoWhere.com> - 2021-03-07 09:55 -0600
  Refuting the halting problem proofs with fully operational code olcott <NoOne@NoWhere.com> - 2021-03-09 10:26 -0600
    Re: Refuting the halting problem proofs with fully operational code (pathological self-reference error) olcott <NoOne@NoWhere.com> - 2021-03-09 11:54 -0600
  Re: Detecting infinite recursion (2021-03-09) olcott <NoOne@NoWhere.com> - 2021-03-09 19:42 -0600

csiph-web