图灵机可判定性模棱两可的情况
Turing machine decidability ambiguous cases
1) 是接受语言L = {ε}的图灵机M，不接受入口吗？
一方面，我认为它可能是假的，因为空词可能是一个条目，但另一方面，我认为这可能是一个无法确定的问题。
2) 是否所有语言可判定的图灵机都在任何输入上停止？
同样的想法，直觉上我会说是的，由于可判定的定义，但我不知道，有些事情困扰我。
3) 无论什么字母表，回文的语言都是可判定的吗？
对于这道题，我几乎毫不怀疑它是假的，因为有了赖斯定理我们可以证明，这道题是不可判定的。
1) 我不确定如何解析它，但如果 TM 接受只包含空集的语言，它最终会在空白磁带上停止接受。这是否算作一个条目取决于您对 "entry" 的定义。我会把它算作一个条目，所以我会回答 "no".
2) 仅由空字符串组成的语言是可判定的。然而，我们可以编写一个 TM，它只接受空字符串并进入无限循环以获取所有其他输入。 "whose language" 的含义值得商榷，但对于编码部分函数的 TM，我会将该 TM 的语言称为它停止接受的字符串集，所以我会回答 "no".
3) 在我看来，给定一个带有 n 个符号的字母表，你总是可以构造一个具有 O(n) 状态的单带确定性 TM，它停止接受该字母表上的回文并停止拒绝其他字符串，从而决定了字母表中回文的语言。我会回答 "yes"，只要这些术语具有通常的含义即可。请注意，莱斯定理不适用；它适用于决定 TM 是否接受字母表上的回文语言的问题，但实际上决定某物是否是回文当然是可能的（PDA 可以做到）。
1) 是接受语言L = {ε}的图灵机M，不接受入口吗？
一方面，我认为它可能是假的，因为空词可能是一个条目，但另一方面，我认为这可能是一个无法确定的问题。
2) 是否所有语言可判定的图灵机都在任何输入上停止？
同样的想法，直觉上我会说是的，由于可判定的定义，但我不知道，有些事情困扰我。
3) 无论什么字母表，回文的语言都是可判定的吗？
对于这道题，我几乎毫不怀疑它是假的，因为有了赖斯定理我们可以证明，这道题是不可判定的。
1) 我不确定如何解析它，但如果 TM 接受只包含空集的语言，它最终会在空白磁带上停止接受。这是否算作一个条目取决于您对 "entry" 的定义。我会把它算作一个条目，所以我会回答 "no".
2) 仅由空字符串组成的语言是可判定的。然而，我们可以编写一个 TM，它只接受空字符串并进入无限循环以获取所有其他输入。 "whose language" 的含义值得商榷，但对于编码部分函数的 TM，我会将该 TM 的语言称为它停止接受的字符串集，所以我会回答 "no".
3) 在我看来，给定一个带有 n 个符号的字母表，你总是可以构造一个具有 O(n) 状态的单带确定性 TM，它停止接受该字母表上的回文并停止拒绝其他字符串，从而决定了字母表中回文的语言。我会回答 "yes"，只要这些术语具有通常的含义即可。请注意，莱斯定理不适用；它适用于决定 TM 是否接受字母表上的回文语言的问题，但实际上决定某物是否是回文当然是可能的（PDA 可以做到）。