大米的非语义特性定理

Question

赖斯的定理 告诉我们唯一的 语义 属性 图灵机 （即由计算机计算的函数的属性）我们可以决定的是两个微不足道的属性（即始终为true，并且始终为false）。

但是，图灵机的其他特性是无法决定的。例如，在给定的图灵计算机中存在无法达到状态的属性是不确定的$^{匕首} $。

是否有类似的定理与稻米定理分类相似属性的可决定性？我没有精确的定义。任何涵盖我给出的示例的已知定理对我来说都是有趣的。

$^匕首$，很容易证明该集合是不可决定的 克莱恩的递归/固定点定理.

Answer 1

部分涵盖给定示例的一般定理是，机器的任何$ sigma^0_1 $ - hard属性都是不可决定的。停止问题是$ m $ - 可用于状态可疑性问题，因此表明状态降低性问题是$ sigma^0_1 $ -HARD。

但是，这不是“且仅在”定理的“及时”，例如Rice的定理。如果图灵机索引的每个$ sigma^0_1 $属性都算作计算机的属性，那么就不会有一个很好的特征，因为没有任何很好的表征对哪种re seles tens可以决定RE集的索引。