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


Groups > comp.software-eng > #2602

Re: Detecting infinite recursion

From Kaz Kylheku <563-365-8930@kylheku.com>
Newsgroups comp.theory, comp.lang.c, comp.lang.c++, comp.software-eng
Subject Re: Detecting infinite recursion
Date 2021-03-02 17:46 +0000
Organization A noiseless patient Spider
Message-ID <20210302093944.475@kylheku.com> (permalink)
References <3LadneKdoK8jzKT9nZ2dnUU78T3NnZ2d@giganews.com> <87czwhfr6s.fsf@tigger.extechop.net> <uLSdnZF1Hv7L6aP9nZ2dnUU7-e3NnZ2d@giganews.com>

Cross-posted to 4 groups.

Show all headers | View raw


On 2021-03-02, olcott <NoOne@NoWhere.com> wrote:
> On 3/2/2021 10:36 AM, Otto J. Makela wrote:
>> I'm a bit late to the discussion, but this sounds a lot like you're
>> trying to overturn Turing's proof that that a general algorithm to solve
>> the halting problem for all possible program-input pairs cannot exist.
>> 
>
> Yes. The key brand new insight that I had about this proof is that the 
> actual execution trace never reaches the undecidable portion, thus 

The program has no "undecidable portion". We know perfectly well
whether it terminates or not, because it is trivial.

All that is undecidable, in the context of computability, is the problem
of determining whether any program whatsoever on any input terminates.

"Undecidable

> making the conventional halting problem counter-examples {Linz, Sipser, 
> Kozen} decidable.

Each such example is individually decidable, and everybody knows this.

No example of anything even moderately hard to decide is ever presented
in the proofs.

> // P has the machine address of H_Hat()
> void H_Hat(u32 P)
> {
>    u32 Input_Halts = Halts(P, P);
>    if (Input_Halts)
>      HERE: goto HERE;
>    return;
> }

Everyone, including probably most CS undergrads by the time they reach
senior year, that if Halts decides that it's a good idea to "decide"
halting by simply running the code, runaway recursion will occur.

When I first encountered the halting problem concept, I remember that
the text I was reading mentioned this: if the decision function jus
executes the function, it precipitates into infinite regress, and
therefore does not terminate, in which case there is no decision.

You have not discovered anything.

Also, the idea of an insruction stream that has no branches corresponds
to the well-known concept of a basic block in program control flow
analysis, used in compilers. Again, something even CS undergrads know by
the time they graduate.

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

Back to comp.software-eng | 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 olcott <NoOne@NoWhere.com> - 2021-02-27 14:20 -0600
  Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 14:40 -0600
    Re: Detecting infinite recursion olcott <NoOne@NoWhere.com> - 2021-02-27 21:30 -0600
    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-03-01 21:32 -0600
          Re: Detecting infinite recursion (H_Hat is proved to be decidable) olcott <NoOne@NoWhere.com> - 2021-03-03 15:37 -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 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 (credit where it is due) olcott <NoOne@NoWhere.com> - 2021-03-02 18:45 -0600
      Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 20:40 -0600
        Re: Detecting infinite recursion (halt decider spec) Richard Damon <Richard@Damon-Family.org> - 2021-03-02 21:57 -0500
          Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 21:03 -0600
            Re: Detecting infinite recursion (halt decider spec) olcott <NoOne@NoWhere.com> - 2021-03-02 21:05 -0600
            Re: Detecting infinite recursion (halt deciding criteria) olcott <NoOne@NoWhere.com> - 2021-03-03 15:50 -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 (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: Detecting infinite recursion (2021-03-09) olcott <NoOne@NoWhere.com> - 2021-03-09 19:42 -0600

csiph-web