非セマンチックな特性の米の定理

Question

ご飯の定理 唯一のことを教えてください セマンティック の性質 チューリングマシン （つまり、マシンによって計算された関数のプロパティ）私たちが決定できるのは、2つの些細なプロパティ（つまり、常に真であり、常にfalse）です。

しかし、却下できないチューリングマシンには他の特性があります。たとえば、特定のチューリングマシンに到達不可能な状態があるという特性は、$^{ dagger} $です。

同様の特性の決定可能性を分類する同様の定理とライスの定理はありますか？正確な定義はありません。私が与えた例をカバーする既知の定理は、私にとって興味深いでしょう。

$^ dagger $このセットが使用されないことを証明するのは簡単です Kleeneの再帰/固定点定理.

Answer 1

与えられた例を部分的にカバーする一般的な定理は、マシンの$ sigma^0_1 $ hardプロパティが決定できないということです。停止の問題は、$ m $を国家の到達可能性の問題に還元可能であるため、状態削減の問題は$ sigma^0_1 $ -HARDであることを示しています。

しかし、これは「もしそうな」定理のような「もし」ではありません。チューリングマシンのインデックスの$ sigma^0_1 $のプロパティがマシンのプロパティとしてカウントされる場合、reセットが用語で決定可能である素晴らしい特性評価がないため、素晴らしい特性評価はありません。 REセットのインデックスの。