turing-machines - L = {T | T は {00, 01}} を認識するチューリング マシンです。L が決定不能であることを証明します。

Question

L = {<T> | T は {00, 01}} を認識するチューリング マシンです。

L が決定不能であることを証明します。

ここで使用する削減を理解することさえ本当に困難です。

私は無料の昼食を求めているのではなく、正しい方向へのプッシュを求めているだけです.

Answer 1

ライスの定理を直接適用すると、何もせずにこれを証明できます。

一部のチューリング マシンは {00, 01} を認識します。そうでない人もいます。違いは、オートマトンの構造ではなく、受け入れられる文字列に関係しているという点でセマンティックです。したがって、ライスの定理により、この集合は決定不能です。