Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2602
| 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.
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
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