Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.software-eng > #2590
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Newsgroups | comp.theory, comp.software-eng, comp.lang.c, comp.lang.c++ |
| Subject | Re: Detecting infinite recursion |
| Followup-To | comp.theory |
| Date | 2021-02-27 01:58 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20210226175333.826@kylheku.com> (permalink) |
| References | <3LadneKdoK8jzKT9nZ2dnUU78T3NnZ2d@giganews.com> |
Cross-posted to 4 groups.
Followups directed to: comp.theory
On 2021-02-26, olcott <NoOne@NoWhere.com> wrote:
> (1) We know that every software function invoked with the same data must
> have the same execution trace.
>
> (2) When a software function invokes itself this is recursive invocation.
>
> (3) When the second recursive invocation of a software function calls
> itself with the same data as the prior invocation then it must have the
> same execution trace as the prior invocation.
>
> (4) When the second recursive invocation of a software function calls
> itself with the same data has no conditional branch instructions
> inbetween these two invocations then this is a case of infinite recursion.
>
> (5) When the recursive invocation is replaced with a call to a software
> system that simulates the execution of the calling function with its
> same data, then this is equivalent to a recursive invocation.
>
> // P has address of H_Hat
> void H_Hat(u32 P)
> {
> Simulate(P, P);
> }
>
> Does everyone agree?
If Simulate(P, P) replaces P(P), and the simulation is a faithful
replica of the processor, then nothing has changed.
You have previosuly written about a scheme in which Simulate
contains provisions for monitoring the execution. An outer Simulate has
instruction stream information from all inner Simulate calls and is able
to impose the rule that the simulation will only go to some fixed number
of levels, like 3. Let's call that N.
Firstly, what that does is change H_Hat: H_Hat is no longer infinitely
recursive, because Simulate detects an internal halting condition and
stops.
Secondly, the different recursion levels of H_Hat are not equivalent
to each other.
The outer-most H_Hat goes to N levels of recursion/simulation nesting.
The next lower nesting, though ostensibly executing the same logic,
only has N-1 remaining levels available to it before it will be
terminated.
The one after that N-2.
A function that terminates after U nestings is not the same function
as a similar one which terminates after V nestings, for U != V.
We must treat each H_Hat invocation at every nesting level i as a
different function H_Hat_i.
--
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