turing-machines - L = {T | T 是识别 {00, 01}} 的图灵机 证明 L 不可判定

Question

L = {<T> | T 是识别 {00, 01}} 的图灵机

证明 L 是不可判定的。

我真的很难理解这里使用的减少。

我不是要免费午餐，只是朝着正确的方向前进。

Answer 1

赖斯定理的直接应用将使您无需做任何工作即可证明这一点。

一些图灵机可以识别 {00, 01}。有些没有。区别在于语义，因为它与接受的字符串有关，而不是自动机的结构。因此，根据赖斯定理，这个集合是不可判定的。