Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #160225
| From | Kaz Kylheku <563-365-8930@kylheku.com> |
|---|---|
| Newsgroups | comp.lang.c, comp.lang.c++, comp.theory |
| Subject | Re: Infinite recursion detection criteria (agreement check) |
| Followup-To | comp.lang.c |
| Date | 2021-04-19 16:59 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <20210419093129.383@kylheku.com> (permalink) |
| References | (18 earlier) <vtKdnQb2zr-d1uH9nZ2dnUU78Q2dnZ2d@giganews.com> <fb0f032d-2e36-45fa-b95e-7b41e82db4d2n@googlegroups.com> <k9mdnakMZo6f9-H9nZ2dnUU7-T3NnZ2d@giganews.com> <20210418152814.400@kylheku.com> <HZednf4MHaCoROH9nZ2dnUU7-dPNnZ2d@giganews.com> |
Cross-posted to 3 groups.
Followups directed to: comp.lang.c
["Followup-To:" header set to comp.lang.c.] On 2021-04-19, olcott <NoOne@NoWhere.com> wrote: > On 4/18/2021 5:57 PM, Kaz Kylheku wrote: >> ["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. > I am rephrasing what I am saying to make it more clear: > > (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(). These conditions imply runaway recursion. Since X was called with certain arguments, and that resulted in Y being called, such that X can be called again with those same arguments, it means that X doesn't stop the recursion. (I wouldn't say infinite recursion, since we are talking about a conrete implementation with concepts like "machine address". It is actually infinite if X and Y tail call each other, otherwise it is runaway recursion that will exhaust the stack.) > > When X() simulates the machine language of Y() and examines resulting > execution trace If X has access to accumulated instruction traces from a prior invocation of X, then it is not a function. It is an imperative procedure with side effects. To be a function, X must instantiate a new trace context each time it is called, which contains no prior traces. If you'd like to discuss an imperative procedure in the context of computability theoiry, it behooves you to convert it to an equivalent function. This is easily doable: you identify all of the state which the procedure mutates, and turn that into a pure calculation, mapping the prior state to the new state. Then you make the old state a function parameter, and the new state part of the return value. If you'd like X to have access to past execution traces, they must be bundled in an argument, which Y passes to X. X can re turn the newly updated execution traces back to Y, which can pass them to X again. However, then we see that (2) is violated "with the same parameters to X". If Y passes two different states to X with different execution trace contents, (2) does not hold. That's the point of the exercise! By insisting on pure functions, we flush out errors of reasoning of this sort, whereby there are "invisible" inputs that we re not taking into account. Because all imperative procedures can be refactored into functions, every theoretical result that we prove about functions holds for imperative procedures. We do not lose any generality; rather, we gain analytic ability.
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 (correct C code) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-04-18 16:14 -0700
Re: Infinite recursion detection criteria (correct C code) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-19 17:01 +0000
Re: Infinite recursion detection criteria (correct C code) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2021-04-19 13:13 -0700
Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 18:23 -0500
Re: Infinite recursion detection criteria (correct C code) Jeff Barnett <jbb@notatt.com> - 2021-04-18 18:11 -0600
Re: Infinite recursion detection criteria (correct C code) olcott <NoOne@NoWhere.com> - 2021-04-18 19:25 -0500
Re: Infinite recursion detection criteria (correct C code) "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2021-04-18 18:04 -0700
Re: Infinite recursion detection criteria (correct C code) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-04-19 04:01 -0700
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 (agreement check) olcott <NoOne@NoWhere.com> - 2021-04-19 12:27 -0500
Re: Infinite recursion detection criteria (agreement check) Kaz Kylheku <563-365-8930@kylheku.com> - 2021-04-19 17:40 +0000
Re: Infinite recursion detection criteria (correct C code) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2021-04-19 04:06 -0700
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