metaprogramming - 計算可能性と複雑さの適用

Question

計算可能性と複雑性を扱うアプリケーションの開発を考えています。機能の最初のリストは次のとおりです。

1. 関数を受け取り、それが計算可能かどうか (つまり、R,RE,coRE に属しているかどうか) をチェックします。
2. 計算可能な関数を受け取り、それがどの複雑度クラスに属しているかを確認します。

そしてもう少し、これは多かれ少なかれ方向です。
このようなアプリケーションに精通していますか?
もしそうなら、このプログラムの機能は何ですか?どこで見つけることができますか?また、このプログラムに欠けている、またはうまく機能しない新しい機能について考えることはできますか?

Answer 1

いいえ、プログラムにチェックさせたいものが決定できないため、これを行うプログラムはありません。決定不能を証明する最も簡単な部分は、関数がRにあるかどうかをチェックすることです。

関数がRにあるかどうかを判断できれば、停止性問題も簡単に判断できます（関数が入力をハードコードし、実際の引数を無視することを除いて同じように機能する場合にのみ、関数fは入力で停止します、はR）にありますが、もちろんできません。xf'fx