Question

Closed. This question needs details or clarity. It is not currently accepting answers.

通过

Closed yesterday.

This post was edited and submitted for review 22 mins ago.

问题的目的是确定检测有限再次入侵所需的最低正确终止状态标准,因为我们假设所涉职能是纯功能(可计算的职能)。

#include <stdint.h>
typedef int(*ptr)(); 

int X(ptr P, ptr I)  
{
  P(I); 
  return 0; 
}

int Y(ptr P)  
{
  X(P, P);
  return 1; 
}

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.

www.un.org/Depts/DGACM/index_spanish.htm 在计算机编程中,纯粹的职能具有以下特性:

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

Answer 1

Since main doesn t use the return value (and neither do the others) is it valid for the problem to replace the return types of X and Y with void (and remove the return statements)? This would be the first step in a proof (which I believe is possible). – Craig Estey

Yes that would be valid. – polcott

Caveat: I ve never done a formal proof before, but I ll make an attempt using code equivalent substitutions that I understand.

步骤概述:

original code
convert return types to void and remove return statements
because all calls to X use the same value for each argument, convert X to use a single argument
inline X into Y
replace all Y with X because they are the same
remove Y
since X is called (only in main) with argument X, replace the argument to X in X with X (i.e. P --> X)
since X no longer depends on its argument, remove the argument

// step1 -- original code

#include <stdint.h>
typedef int (*ptr) ();

int
X(ptr P, ptr I)
{
    P(I);
    return 0;
}

int
Y(ptr P)
{
    X(P, P);
    return 1;
}

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

// step2 -- convert return types to void and remove return statements

#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);
}

// step3 -- because all calls to X use the same value for each argument,
// convert X to use a single argument

#include <stdint.h>
typedef void (*ptr) ();

void
X(ptr P)
{
    P(P);
}

void
Y(ptr P)
{
    X(P);
}

int
main()
{
    X(Y);
}

// step4 -- inline X into Y

#include <stdint.h>
typedef void (*ptr) ();

void
X(ptr P)
{
    P(P);
}

void
Y(ptr P)
{
    P(P);
}

int
main()
{
    X(Y);
}

// step5 -- replace all Y with X because they are the same

#include <stdint.h>
typedef void (*ptr) ();

void
X(ptr P)
{
    P(P);
}

void
Y(ptr P)
{
    P(P);
}

int
main()
{
    X(X);
}

// step6 -- remove Y

#include <stdint.h>
typedef void (*ptr) ();

void
X(ptr P)
{
    P(P);
}

int
main()
{
    X(X);
}

// step7 -- since X is called (only in main) with argument X, replace the
// argument to X in X with X (i.e. P --> X)

#include <stdint.h>
typedef void (*ptr) ();

void
X(ptr P)
{
    X(X);
}

int
main()
{
    X(X);
}

// step8 -- since X no longer depends on its argument, remove the argument

#include <stdint.h>
typedef void (*ptr) ();

void
X(void)
{
    X();
}

int
main()
{
    X();
}

在最后步骤中,<代码>main 电话X。和X 仅指自己[最后]。

<><>UPDATE:

The original X and Y are reduced to X calling itself, thus proving that Y calls X in infinite recursion. What I really need to know is whether or not it can be correctly determined that Y calls X in infinite recursion on the basis that Y is calling its caller with the same parameters as it caller. – polcott

我并不完全相信我理解你再次提出的要求。但我认为,以上证据的[或副产品]意味着这一点。

Perhaps, if we redo step (5) as:

// alt5 -- replace X(Y) in main with Y(X)

#include <stdint.h>
typedef void (*ptr) ();

void
X(ptr P)
{
    P(P);
}

void
Y(ptr P)
{
    P(P);
}

int
main()
{
    Y(X);
}

现在我们可以尝试:

// alt6 -- replace [undo] P(P) in Y with X(P)

#include <stdint.h>
typedef void (*ptr) ();

void
X(ptr P)
{
    P(P);
}

void
Y(ptr P)
{
    X(P);
}

int
main()
{
    Y(X);
}

我们最后以呼吁顺序:

main -> Y(X)
Y(X) -> X(X)
X(X) -> X(X)

我不知道,但如果我们在第(3)步后停职,并修改了<条码>>>,则“m>可<>>。

友情链接