混淆理论和符号计算

Question

是否有任何文档或特定文本描述了生成功能等效但语义不同的计算机程序的理论基础？理想情况下，我正在寻找涵盖从与KLEE相同的脉络中为实际编程语言的离散指令派生符号指令的基础的文档。

我很好奇，如果在确定两段代码是否共享等效连续执行状态的某些子集时存在复杂度的下界，即state @指令指针和同时存在的全局变量，堆栈和堆值。

Answer 1

对于第一个问题，您可能有兴趣研究polymorphic code，这是您描述的功能的子集。

对于第二个问题：

确定是否两段代码是功能上等同的是硬如所述停机问题，这是一个公知的不可判定问题 - 没有计算机都不能解决它针对问题的所有情况。

要看到这一点，请注意，我们可以通过询问待测程序是否与不停机程序for(;;);具有相同的功能来解决暂停问题。我们忽略了副作用，所以我们不在乎该程序是否同时做了其他事情 - 我们关心的是它是否最终完成。