Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c++ > #79062
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Newsgroups | comp.theory, comp.lang.c, comp.lang.c++ |
| Subject | Re: Infinite recursion detection criteria (correct C code) |
| Followup-To | comp.lang.c |
| Date | 2021-04-18 22:57 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20210418152814.400@kylheku.com> (permalink) |
| References | (18 earlier) <Ua6dnXWIW-ybs-b9nZ2dnUU7-WvNnZ2d@giganews.com> <xYUeI.8111$v3H9.971@fx01.iad> <vtKdnQb2zr-d1uH9nZ2dnUU78Q2dnZ2d@giganews.com> <fb0f032d-2e36-45fa-b95e-7b41e82db4d2n@googlegroups.com> <k9mdnakMZo6f9-H9nZ2dnUU7-T3NnZ2d@giganews.com> |
Cross-posted to 3 groups.
Followups directed to: comp.lang.c
["Followup-To:" header set to comp.lang.c.] On 2021-04-18, olcott <NoOne@NoWhere.com> wrote: > On 4/18/2021 12:08 PM, Malcolm McLean wrote: >> On Sunday, 18 April 2021 at 16:06:43 UTC+1, olcott wrote: >>> On 4/18/2021 6:44 AM, Richard Damon wrote: >>>> On 4/17/21 2:50 PM, olcott wrote: >>>>> On 4/17/2021 1:29 PM, Malcolm McLean wrote: >>> >>>>>> Because H deals with a notation for H_Hat, not H_Hat itself (I know PO >>>>>> has fudged >>>>>> this), >>>>> >>>>> It is not fudging to say that source code is interpreted rather than >>>>> compiled. >>>> >>>> Just remember that H^ has a COPY of halt, not a 'call' to the version >>>> that is in the halt decider. >>> >>> Just remember that I have and continue to stipulate otherwise. >>> >> This is one of those things like insisting on putting the hat in the >> microwave before extracting the rabbit. It's legitimate in itself, but >> it's eccentric, and it opens the door wide open to cheating. >> >> You can insist on x86 code instead of a Turing machine, you can even >> reference external subroutine calls in the code. But the arrangement >> means that is now extremely easy to use data that the Turing machine >> does not have. >> > > Look at it instead as C / x86 such that function X() in C that always > simulates its input detects when itself is called in infinite recursion. > > If the execution trace of function X() called by function Y() shows: > (1) Function X() is called twice in sequence from the same machine > address of Y(). > (2) With the same parameters to X(). > (3) With no conditional branch or indexed jump instructions in Y(). > (4) With no function call returns from X(). > then the function call from Y() to X() is infinitely recursive unless > X() stops it. I have two remarks. Remark 1: This argument is irrefutable, because it is vacuously true. Y has no power to stop the recursion because of (3). Therefore, the only that there might be no recursion is if X stops it. Thus, whenever (3) holds, the conclusion says, effectively, "the function call is infinitely recursive, or else it is not infinitely recursive", which is vacuously true. THe only way we can disprove an argument is if we show that its conclusion is false when the premises are true. If we hold the premises true, (3) must be true since it is one of them, and in that situation, the conclusion is vacuously true. Remark 2: There is no way for the premises to be true, and for there not to be runaway recursion. Therefore the "unless X stops it" remark in the conclusion is superfluous: it refers to an impossible situation. Proof: If all the premises are true, then (3) is true. Thus only X can stop the recursion. Hypothesis: suppose X does stop the recursion. X is a function, which means it can only make a decision based on its parameters and nothing else. Whenever it is called with the same parameters, it performs the same computational steps. (2) that X is called with the same parameters by Y. Therefore if X stops the recursion, X does that on the first call from Y. Y is not called again, and so there is no second call from Y to X. But this contradicts (1), which asserts that there are two calls to X. Therefore, we must retract our hypothesis: X does not stop the recursion. That leads to a contradiction. -- TXR Programming Language: http://nongnu.org/txr Cygnal: 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
Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 12:19 -0500
Re: Infinite recursion detection criteria (correct C code) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-18 22:57 +0000
Re: Infinite recursion detection criteria (agreement check) olcott <NoOne@NoWhere.com> - 2021-04-18 20:13 -0500
Re: Infinite recursion detection criteria (agreement check) olcott <NoOne@NoWhere.com> - 2021-04-18 20:16 -0500
Re: Infinite recursion detection criteria (agreement check) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-19 16:59 +0000
Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 21:16 -0500
Re: Infinite recursion detection criteria (correct C code) Richard Damon <Richard@Damon-Family.org> - 2021-04-18 22:26 -0400
Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 21:29 -0500
Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-19 10:40 -0500
csiph-web