言語の長さが 2 で割られることを簡約法を使用して証明するにはどうすればよいですか? L={ | は |L(M)|= 0 mod 2 のチューリング マシンです}
私には2つのアイデアがありますが、間違ったものに従うことを恐れています0 mod 2 。
2) NOT HALT でリダクション法を使用し、チューリングマシンは入力を拒否すると言うので、チューリングマシンの長さは 0 になり、上記の条件を満たします!
なにか提案を ？
質問する
1278 次