metaprogramming - 可计算性和复杂性应用

Question

我正在考虑开发一个处理可计算性和复杂性的应用程序。它的初始功能列表将是：

1. 接收一个函数并检查它是否可计算（即它是否属于R、RE、coRE）。
2. 接收可计算函数并检查它属于哪个复杂性类。

还有更多，这或多或少是一个方向。
你熟悉这样的应用程序吗？
如果是这样，该程序的功能是什么，我在哪里可以找到它，您能想到该程序缺少的或无法正常运行的新功能吗？

Answer 1

不，没有程序可以执行此操作，因为您希望程序检查的内容无法确定。最容易证明不可判定的部分是检查一个函数是否在 R 中：

如果您可以确定一个函数是否在 R 中，您也可以轻松确定停止问题（当且仅当该函数f在输入上停止时，该函数的工作原理与它对输入进行硬编码并忽略其实际参数相同） , 在 R) 中，当然你不能。xf'fx