Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Re: Infinite recursion detection criteria (correct C code)

33 views
Skip to first unread message

olcott

unread,
Apr 18, 2021, 1:19:14 PM4/18/21
to
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.

Everything that has been alluded to as cheating is simply correct C code
correctly deciding that it has been called in infinite recursion on the
basis of examining the x86 execution trace of its caller according to
the above criteria.

--
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre
minds." Einstein

Kaz Kylheku

unread,
Apr 18, 2021, 6:57:57 PM4/18/21
to
["Followup-To:" header set to comp.lang.c.]
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

Keith Thompson

unread,
Apr 18, 2021, 7:14:12 PM4/18/21
to
Kaz Kylheku <563-36...@kylheku.com> writes:
> ["Followup-To:" header set to comp.lang.c.]

Why??

> On 2021-04-18, olcott <No...@NoWhere.com> wrote:
[...]

--
Keith Thompson (The_Other_Keith) Keith.S.T...@gmail.com
Working, but not speaking, for Philips Healthcare
void Void(void) { Void(); } /* The recursive call of the void */

olcott

unread,
Apr 18, 2021, 7:24:01 PM4/18/21
to
void X(u32 P, i32 I)
{
Simulate(P, I);
}

void Y(u32 P)
{
X(P, P);
}

int main()
{
X((u32)Y, (u32)Y);
}

When X() simulates the machine language of Y() and examines resulting
execution trace after simulating each machine instruction of Y() then
X() can apply the criteria provided in the prior answer to stop
simulating Y() on the basis that Y() would otherwise cause X() have
infinite execution.

Thus providing the software engineering basis that Halts() does
correctly decide that it must abort the simulation of H_Hat() to prevent
its own infinite execution.

Jeff Barnett

unread,
Apr 18, 2021, 8:12:00 PM4/18/21
to
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.

Interesting question given the use of a simulator: How much is really
simulated?
--
Jeff Barnett

olcott

unread,
Apr 18, 2021, 8:25:24 PM4/18/21
to
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.

Chris M. Thomasson

unread,
Apr 18, 2021, 9:04:14 PM4/18/21
to
Wait a minute... Are you coding the simulator, or not?

olcott

unread,
Apr 18, 2021, 9:13:40 PM4/18/21
to
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().

void X(u32 P, i32 I)
{
Simulate(P, I);
}

void Y(u32 P)
{
X(P, P);
}

int main()
{
X((u32)Y, (u32)Y);
}

When X() simulates the machine language of Y() and examines resulting
execution trace after simulating each machine instruction of Y() then
X() can apply the criteria provided in the above to stop simulating Y()
on the basis that Y() would otherwise cause X() have infinite execution.

Do you agree with all that?

olcott

unread,
Apr 18, 2021, 9:16:26 PM4/18/21
to
Infinite recursion detection criteria:

olcott

unread,
Apr 18, 2021, 10:17:11 PM4/18/21
to
On 4/18/2021 9:13 PM, Richard Damon wrote:
> On 4/18/21 9:27 PM, olcott wrote:
>> On 4/18/2021 6:35 PM, Richard Damon wrote:
>>> On 4/18/21 7:16 PM, olcott wrote:
>>>> On 4/18/2021 4:58 PM, Richard Damon wrote:
>>>>> On 4/18/21 5:43 PM, olcott wrote:
>>>>>> On 4/18/2021 4:37 PM, Richard Damon wrote:
>>>>>>> On 4/18/21 4:17 PM, olcott wrote:
>>>>>>>> On 4/18/2021 2:59 PM, Richard Damon wrote:
>>>>>>>>> On 4/18/21 3:43 PM, olcott wrote:
>>>>>>>>>> On 4/18/2021 2:36 PM, Richard Damon wrote:
>>>>>>>>>>> The problem here is you are ignoring the definition of
>>>>>>>>>>> Computations.
>>>>>>>>>>
>>>>>>>>>> This is not a problem at all because I am only referring to the
>>>>>>>>>> simple
>>>>>>>>>> fact that my C code does do what I claim that it does do.
>>>>>>>>>
>>>>>>>>> No, you CLAIM that you are proving an error in Theories about
>>>>>>>>> Computation Theory. If you don't follow the rules of Computation
>>>>>>>>> Theory
>>>>>>>>> that is not true.
>>>>>>>>>>
>>>>>>>>>> The commercial purpose of a halt decider is to detect programs
>>>>>>>>>> that
>>>>>>>>>> would not otherwise halt and abort these programs to prevent
>>>>>>>>>> things
>>>>>>>>>> such
>>>>>>>>>> as a denial-of-service attack.
>>>>>>>>>>
>>>>>>>>>
>>>>>>>>> But that is not the purpose of the Halting Theory of Conventional
>>>>>>>>> Computaiton Theory.
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>> My C code proves that the conventional halting problem
>>>>>>>>>> undecidability
>>>>>>>>>> proof counter-example does not prevent such a denial-of-service
>>>>>>>>>> attack
>>>>>>>>>> program from being created.
>>>>>>>>>
>>>>>>>>> The Conventional Halting Problem never claimed to prevent DOS
>>>>>>>>> attacks.
>>>>>>>>>
>>>>>>>>> It claimed that we can not always predict if a given potentially
>>>>>>>>> long
>>>>>>>>> running computation will eventually end.
>>>>>>>>>
>>>>>>>>
>>>>>>>> That a program X can correctly decide whether or not another
>>>>>>>> program Y
>>>>>>>> is calling X in what would otherwise be infinite recursion <is>
>>>>>>>> computationally equivalent to a halt decider whether you understand
>>>>>>>> this
>>>>>>>> or not.
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>> Wrong. The fact that when Y() calls X() that X() will decide to limit
>>>>>>> the recursion makes Y() not have infinite-recursion.
>>>>>>>
>>>>>>> The fact that the outer X() can't deduce this properly is a
>>>>>>> failure of
>>>>>>> X().
>>>>>>>
>>>>>>
>>>>>> Yes of source you say very stupid things like this when you merely
>>>>>> glance at a few of my words before artificicially contriving a what
>>>>>> might appear to be a rebuttal to someone that is hardly paying any
>>>>>> attention at all.
>>>>>>
>>>>>> what would otherwise be infinite recursion
>>>>>> what would otherwise be infinite recursion
>>>>>> what would otherwise be infinite recursion
>>>>>> what would otherwise be infinite recursion
>>>>>
>>>>>
>>>>> We don't care about 'otherwise...'
>>>>
>>>> "Otherwise" is an integral part of the criteria, if you don't care about
>>>> otherwise then you are simply ignoring my criteria rather than
>>>> critiquing it.
>>>>
>>>> I will try to formalize it a little better:
>>>> Does X() stop simulating Y() on the basis of:
>>>>
>>>> (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().
>>>>
>>>
>>> It becomes a matter of definition, and because of the context of your
>>> comments that context is fairly obvious, especially since it is present
>>> upthread.
>> void X(u32 P, i32 I)
>> {
>> Simulate(P, I);
>> }
>>
>> void Y(u32 P)
>> {
>> X(P, P);
>> }
>>
>> int main()
>> {
>> X((u32)Y, (u32)Y);
>> }
>>
>> When X() simulates the machine language of Y() and examines resulting
>> execution trace after simulating each machine instruction of Y() then
>> X() can apply the criteria provided in the above to stop simulating Y()
>> on the basis that Y() would otherwise cause X() have infinite execution.
>>
>> Do you agree with this?
>>
>>
>
> With the code provided here, X has no conditions at all,

No try again you are not paying close enough attention, it never says
that X() has no conditional code.

Richard Damon

unread,
Apr 18, 2021, 10:26:58 PM4/18/21
to
But X() was defined as:

>>> void X(u32 P, i32 I)
>>> {
>>> Simulate(P, I);
>>> }
>>>

You have previous defined that Simulate is a regular UTM function.

I see no conditional in that function.


Your logic in inconsistent.

olcott

unread,
Apr 18, 2021, 10:29:37 PM4/18/21
to
I have never ever defined X() as a UTM anything. X has always only been
C code. You have to pay attention to what I am actually saying not what
you think that I mean.

Tim Rentsch

unread,
Apr 19, 2021, 7:01:20 AM4/19/21
to
Jeff Barnett <j...@notatt.com> writes:

[...]

> 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.
>
> Interesting question given the use of a simulator: How much is
> really simulated?

Since neither the thoughts nor the discussion preceding them has
anything to do with the C programming language, they should be
posted somewhere else, and not in comp.lang.c.

Tim Rentsch

unread,
Apr 19, 2021, 7:06:32 AM4/19/21
to
Kaz Kylheku <563-36...@kylheku.com> writes:

> On 2021-04-18, olcott <No...@NoWhere.com> wrote:

[...]

> I have two remarks. [...]

If you are going to keep responding to this idiot, please limit
the posted responses to newsgroups where they are topical, which
does not include either comp.lang.c or comp.lang.c++.

olcott

unread,
Apr 19, 2021, 11:40:26 AM4/19/21
to
On 4/19/2021 10:28 AM, Richard Damon wrote:
> On 4/19/21 11:12 AM, olcott wrote:
>> On 4/19/2021 6:16 AM, Richard Damon wrote:
>>>>>>> void X(u32 P, u32 I)
>>>>>>> {
>>>>>>> Simulate(P, I);
>>>>>>> }
>>>>>>>
>>>>
>>>> You have previous defined that Simulate is a regular UTM function.
>>>>
>>>> I see no conditional in that function.
>>>>
>>>>
>>>> Your logic in inconsistent.
>>>>
>>>
>>> I never said X was a UTM anything. READ THE THREAD. I said X had no
>>> conditions in it.
>>>
>>>
>>> See THIS comment upthread?
>>>>> No try again you are not paying close enough attention, it never says
>>>>> that X() has no conditional code.
>>>
>>>
>>> Maybe YOU should stop and read a bit more.
>>>
>>> Maybe you should also watch about reusing names that mean different
>>> things or tryng to hide code
>>>
>>
>> I never ever said that X() was any kind of UTM this whole analysis with
>> X() and Y() is strictly a C program that analyzes the x86 execution
>> trace of its simulation of the machine pointed to by P with data pointed
>> to by I.
>>
>
> You sure seem to like fighting straw men.
>
> This sub-thread was NOT about X being a UTM. It was about you talking
> about conditional execution inside X when you provided a definition of
> X() that hand NO conditional execution.
>

Do you have OCD? You keep getting key points incorrectly.

These four points are examined as the basis of determining that Y() is
calling X() in infinite recursion.

I never said that X() does not have conditional branch instructions.

I only said that they are not part of the basis for correctly deciding
that Y() has called X() in infinite recursion.

It turns out that these four points are a sufficient condition for
correctly deciding that Y() is calling X() in infinite recursion.

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

The following code (including an x86 emulator) is written in "C"

void X(u32 P, u32 I)
{
Simulate(P, I);
}

void Y(u32 P)
{
X(P, P);
}

int main()
{
X((u32)Y, (u32)Y);
}

When X() simulates the x86 machine language of Y() and examines
resulting execution trace after simulating each machine instruction of
Y() then X() can apply the criteria provided above to correctly decide
to stop simulating Y() on the basis that Y() would otherwise cause X()
have infinite execution.



Kaz Kylheku

unread,
Apr 19, 2021, 12:59:51 PM4/19/21
to
["Followup-To:" header set to comp.lang.c.]
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.

Kaz Kylheku

unread,
Apr 19, 2021, 1:01:49 PM4/19/21
to
On 2021-04-18, Keith Thompson <Keith.S.T...@gmail.com> wrote:
> Kaz Kylheku <563-36...@kylheku.com> writes:
>> ["Followup-To:" header set to comp.lang.c.]
>
> Why??

My newsreader does that automatically; I usually don't pay attention to
it.

olcott

unread,
Apr 19, 2021, 1:27:23 PM4/19/21
to
Although it may be true that all pure functions are computations it is
apparently not true that computations are limited to only pure functions.

Kaz Kylheku

unread,
Apr 19, 2021, 1:40:17 PM4/19/21
to
On 2021-04-19, olcott <No...@NoWhere.com> wrote:
> Although it may be true that all pure functions are computations it is
> apparently not true that computations are limited to only pure functions.

In the context in which we find ourselves, "computation" and "pure
function" are synonymous. A computation is a transformation of a
specific input (that is defined in every detail, down to the last bit)
to an output.

The only way in which we can regard an imperative procedure as a
computation is by regarding regard the global, mutating state which it
works with to be part of the input.

Note that I am not looking for comments in regard to what I am writing
here; I am simply a messenger, passing on a small bit of standard
education that you are lacking.

I didn't invent that education, so if you have a problem with it, I
invite you to take it up with the tomes laying on the shelves of your
nearest computer science or mathematics library.

Keith Thompson

unread,
Apr 19, 2021, 4:13:36 PM4/19/21
to
Please start paying attention to it. Stop cross-posting olcott-stuff
to comp.lang.c (or comp.lang.c++, or ...).
0 new messages