混淆理論和符號計算

Question

是否有任何文檔或特定文本描述了生成功能等效但語義不同的計算機程序的理論基礎？理想情況下，我正在尋找涵蓋從與KLEE相同的脈絡中爲實際編程語言的離散指令派生符號指令的基礎的文檔。

我很好奇，如果在確定兩段代碼是否共享等效連續執行狀態的某些子集時存在複雜度的下界，即state @指令指針和同時存在的全局變量，堆棧和堆值。

Answer 1

對於第一個問題，您可能有興趣研究polymorphic code，這是您描述的功能的子集。

對於第二個問題：

確定是否兩段代碼是功能上等同的是硬如所述停機問題，這是一個公知的不可判定問題 - 沒有計算機都不能解決它針對問題的所有情況。

要看到這一點，請注意，我們可以通過詢問待測程序是否與不停機程序for(;;);具有相同的功能來解決暫停問題。我們忽略了副作用，所以我們不在乎該程序是否同時做了其他事情 - 我們關心的是它是否最終完成。