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


Groups > comp.lang.c > #160210

Re: Infinite recursion detection criteria (correct C code)

From "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups comp.lang.c
Subject Re: Infinite recursion detection criteria (correct C code)
Date 2021-04-18 18:04 -0700
Organization Aioe.org NNTP Server
Message-ID <s5iku0$bvf$1@gioia.aioe.org> (permalink)
References (18 earlier) <fb0f032d-2e36-45fa-b95e-7b41e82db4d2n@googlegroups.com> <k9mdnakMZo6f9-H9nZ2dnUU7-T3NnZ2d@giganews.com> <20210418152814.400@kylheku.com> <s5ihs4$fgp$1@dont-email.me> <MridnQP9Rc55UOH9nZ2dnUU7-c3NnZ2d@giganews.com>

Show all headers | View raw


On 4/18/2021 5:25 PM, olcott wrote:
> On 4/18/2021 7:11 PM, Jeff Barnett wrote:
>> On 4/18/2021 4: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.
>>>
>>> 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.
>>
>> What about the following thoughts:
>>
>> 1) The architecture of the execution engine provides for traps 
>> (interrupts) to be signaled in cases of arithmetic errors such as 
>> divide by zero, under/over flow, etc. Thus, almost every arithmetic 
>> instruction is an instance of "conditional" execution. Also consider 
>> timer and external signal interrupts and it becomes quite clear that 
>> conditions 1 thru 4 above need context in order to validate any 
>> inferences from them.
> 
> That is really great that is your very first 100% legitimate and 
> technically correct reply to the actual technical question that was asked.
> 
>>
>> Interesting question given the use of a simulator: How much is really 
>> simulated?
> 
> I will try to divide by zero and see how this is handled.
> It looks like that blows up the simulator.
> 

Wait a minute... Are you coding the simulator, or not?

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 (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