1、如果一个语言是________，则存在一个图灵机，对于任何输入字符串，该图灵机都能在有限步内给出是否接受该字符串的决定。

参考答案：可判定（Decidable）

2、如果语言A可归约到语言B，且B是可判定的，那么A一定是_____。

参考答案：可判定的

1、语言 L = {0^k | k 是一个素数} 是可识别的。
参考解答：

2、证明：如果A ≤m B且B ≤m C，那么A ≤m C。（即证明归约关系的传递性）
参考解答：

1、问题：考虑语言L = {<M> | M是一个在空输入上停机的图灵机}。
a) L是图灵可识别的吗？为什么？
b) L是图灵可判定的吗？为什么？

参考解答：
a) L是图灵可识别的。
解析：我们可以构造一个图灵机R来识别L。R在输入<M>上，模拟M在空输入上的运行。如果M停机，R就接受；如果M不停机，R也不会停机。这正好满足图灵可识别的定义。
b) L不是图灵可判定的。
解析：这涉及到停机问题。如果L是可判定的，我们就能解决停机问题，但停机问题是不可判定的。具体来说，如果有一个判定L的图灵机D，我们就可以用它来构造一个解决停机问题的图灵机，这与停机问题的不可判定性相矛盾。