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

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

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

int main() 
{   
  Y(Y);  
}

我正在用 C 语言做计算机科学，因为计算机科学家不这样做，所以我来这里是为了获得更多实际帮助。我需要具体地做计算机科学（用 C 和 x86 机器语言），因为抽象会泄露关键细节。

其机器语言的执行轨迹证明，上述函数从同一个机器地址、同一个输入数据依次被调用至少两次。

是否有任何反例，其中一个函数从同一个机器地址以非无限递归的相同输入按顺序调用两次**？

** 中间可以有任何中间代码
（函数从被调用函数返回到同一调用者除外）。

4

2 回答 2

1

从上面的讨论：
调用函数不访问静态或全局数据作为终止其函数调用序列的基础已被重新解释为如下所示的（3）的第一部分。(3) 的第二部分基于对此答案的评论。

如果函数 Y() 调用的函数 X() 的执行轨迹显示：
(1) 函数 X() 从 Y() 的同一机器地址依次调用两次。
(2) 使用与 X() 相同的参数。
(3) Y() 中没有条件分支或索引跳转指令。
(4) 没有函数调用从 X() 返回到 Y()。
那么从 Y() 到 X() 的函数调用是无限递归的。

如果有人不同意，请在评论中告诉我，我会更新这个答案。

于 2021-04-16T22:04:46.847 回答
0

将原始答案扩展到涵盖模拟：

#define ptr uintptr_t 

void X(ptr P, ptr I)
{
  Simulate(P, I);
}
        
void Y(ptr P) 
{
  X(P, P); 
} 
                    
int main() 
{   
  Y((ptr)Y);  
}

如果函数 Y() 调用的函数 X() 的执行轨迹显示：
(1) 函数 X() 从 Y() 的同一机器地址依次调用两次。
(2) 使用与 X() 相同的参数。
(3) Y() 中没有条件分支或索引跳转指令。
(4) 没有函数调用从 X() 返回到 Y()。
那么从 Y() 到 X() 的函数调用是无限嵌套的模拟。

在无限嵌套模拟的情况下，总是满足规则 (4)，因为没有模拟器每个都返回它正在模拟的输入。

当 X() 模拟 Y() 的机器语言并在模拟 Y() 的每条机器指令后检查生成的执行跟踪时，X() 可以应用上面提供的标准来根据 Y() 指定停止模拟 Y()无限嵌套模拟。

于 2021-04-18T19:15:54.653 回答