On 2/4/24 9:41 AM, olcott wrote:
The purpose of this question is to determine the minimum correct halt
status criteria required to detect infinite recursion, when we assume
that the functions involved are pure functions (thus computable
functions).
#include <stdint.h>
typedef void(*ptr)();
void X(ptr P, ptr I)
{
P(I);
}
void Y(ptr P)
{
X(P, P);
}
int main()
{
X(Y, Y);
}
Does that fact that Y calls its caller with the same parameters as its
caller prove that Y is calling X in infinite recursion?
*When we assume that Y is a pure function*
If there were any conditional branch instructions in Y prior to its call
to X it seems to be proved that they didn't make any difference.
In computer programming, a pure function is a function that has the
following properties:
(1) the function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable
reference arguments or input streams), and
(2) the function has no side effects (no mutation of local static
variables, non-local variables, mutable reference arguments or
input/output streams). https://en.wikipedia.org/wiki/Pure_function
*Computable functions* are the basic objects of study in computability theory. Computable functions are the formalized analogue of the
intuitive notion of algorithms, in the sense that a function is
computable if there exists an algorithm that can do the job of the
function, i.e. given an input of the function domain it can return the corresponding output. https://en.wikipedia.org/wiki/Computable_function#
As you have been told elsewhere, to prove you have infinite recursion,
not only must there be no conditionals in Y, there needs to be no
conditionals in X.
Also, when you later change X into a conditional simulator, that is a
very different thing then an unconditional call to the parameters
defined by its input. (as is clear you are going to want to do)
So, you are going down a dead end.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)