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


Groups > comp.lang.c++ > #79089

Re: Infinite recursion detection criteria (agreement check)

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

Show all headers | View raw


["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


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