L = {T |T 是一个图灵机，它识别 {00， 01}} 证明 L 是不可判定的

Question

L = { |T 是识别 {00， 01}} 的图灵机

证明 L 是不可判定的。

我什至很难理解在这里使用的减少。

我不要求免费午餐，只是朝着正确的方向推动。

Answer 1

直接应用赖斯定理可以让你证明这一点，而无需做任何工作。

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