1) 接受语言 L = {ε} 的图灵机 M 是否不接受任何条目？
一方面，我认为它可能是错误的，因为空词可能是一个条目，但另一方面，我认为这可能是一个无法确定的问题。
2）是否每台可判定语言的图灵机在任何输入时都会停止？
同样的想法，直觉上我会说是的，由于可判定的定义，但我不知道，有什么困扰我。
3）回文的语言是否可以确定，无论 aphabet 是什么？
对于这一点，我几乎毫不怀疑它是错误的，因为有了赖斯定理，我们可以证明，这个问题是不可判定的。
问问题
297 次
1 回答
0
1）我不知道如何解析这个，但如果一个 TM 接受只包含空集的语言，它最终会在空白磁带上停止接受。这是否算作条目取决于您对“条目”的定义。我会把它算作一个条目，所以我会回答“不”。
2) 仅由空字符串组成的语言是可判定的。但是，我们可以编写一个仅接受空字符串并进入所有其他输入的无限循环的 TM。“谁的语言”是什么意思是有争议的，但对于编码部分函数的 TM，我会将该 TM 的语言称为它停止接受的字符串集，所以我会回答“否”。
3）在我看来，给定一个带有 n 个符号的字母表，你总是可以构造一个具有 O(n) 个状态的单磁带确定性 TM，该状态在该字母表上停止接受回文并停止拒绝其他字符串，从而决定字母表上的回文语言。我会回答“是”，只要这些术语具有它们通常的含义。请注意，赖斯定理不适用；它适用于确定 TM 是否接受回文语言而不是字母表的问题，但实际上确定某事是否是回文当然是可能的（PDA 可以做到）。
于 2017-11-27T02:52:57.097 回答