纯函数场景下，Y传相同参数调用调用者能否证明存在无限递归？

本问题旨在确定检测无限递归所需的最小正确停机状态判定标准，前提是涉及的函数均为纯函数（即可计算函数）。

#include <stdint.h>
typedef void(*ptr)(); 
        
01  void X(ptr P, ptr I)  
02  {
03    P(I); 
04  }
05    
06  void Y(ptr P)  
07  {
08    X(P, P);
09  }
10    
11  int main()
12  {
13    X(Y, Y);
14  }

执行轨迹 #

• 第13行：main()调用X(Y, Y);

重复执行 #

• 第03行：X()调用Y(Y);
• 第08行：Y()调用X(Y, Y);

核心问题 #

Y以其调用者的相同参数调用该调用者这一事实，能否单独确凿证明Y与X之间存在无限递归？

纯函数假设 #

即便Y在调用X之前存在条件分支指令，这些分支也不会产生任何影响。

纯函数定义（计算机编程领域） #

纯函数具备以下特性：

• 相同参数对应相同返回值（不受局部静态变量、非局部变量、可变引用参数或输入流影响）；
• 无副作用（不会修改局部静态变量、非局部变量、可变引用参数或输入/输出流）。

可计算函数定义 #

可计算函数是可计算性理论的核心研究对象，是算法直观概念的形式化对应物。即若存在某一算法，可针对函数定义域内的输入返回对应输出，则该函数为可计算函数。

内容的提问来源于stack exchange，提问作者polcott