图灵机可判定性模糊案例

Question

1)是一个图灵机M，它接受语言L= {ε}，不接受输入？

一方面，我认为这可能是错误的，因为空话可能是一个条目，但在另一个，我认为这可能是一个难以确定的问题。

2)是否每台语言可判定的图灵机在任何输入上都会停止?

同样的想法，凭直觉我会说是的，因为可判定性的定义，但我不知道，有些事情困扰着我。

3)回文的语言，无论是哪种语言，都是可判定的吗?

对于这个问题，我几乎毫不怀疑它是错误的，因为用Rice定理，我们可以证明，这个问题是不可判定的。

Answer 1

1)我不知道如何解析这一点，但如果TM接受仅由空集组成的语言，它最终将停止--在空白磁带上接受。这是否算一个条目取决于你对“条目”的定义。我会把它算作一个条目，所以我会回答“不”。

2)仅由空字符串组成的语言是可判定的。然而，我们可以编写一个TM，它只接受空字符串，并为所有其他输入进入一个无限循环。什么是“谁的语言”是有争议的，但对于编码部分函数的TMs，我会把TM的语言称为停止接受的字符串集，所以我会回答“否”。

( 3)在我看来，给定一个有n个符号的字母表，你总是可以构造一个带有O(n)状态的单磁带确定性TM，在该字母表上接受回文并停止--拒绝其他字符串，从而决定回文的语言而不是字母表。只要这些词有其通常的含义，我就会回答“是”。请注意，Rice的定理不适用；它将适用于决定TM是否接受回文语言而不是字母表的问题，但实际上确定某物是否是回文是可能的(PDA会这样做)。