图灵-可判定语言和图灵-可判定机器。不同？

Question

我有一个图灵机M，我已经证明了M不是一个决策者。然后，我已经证明了A=L(M)或M识别的语言A。我现在被问到“语言(A)图灵是可决定的吗”。

我的问题是，如果我已经证明了M不是一个决策者，我能不能用这一点来暗示语言(A)不是图灵可决定的？在我看来，机器M的语言不仅包括可接受的语言，还包括永远不会停止的无限长字符串。这将使语言也不是图灵-可决定的？

谢谢你的建议。

Answer 1

我认为这个问题有一些模棱两可的地方需要澄清。为了与之相提并论，让我澄清一些定义：

定义

图灵判定一种形式语言L称为“-

1. ”，如果它存在一个“决策器”。
2. "decider“是一个TM，它在Sigma-star的所有字符串上停止(Sigma是这个TM的字母)。具体地说，当我们从L(应该被接受)或L-bar (应该被拒绝)输入字符串时，机器停止。请注意，所有这些字符串都来自Sigma-star。我们不允许在Sigma-star之外输入字符串。字符串“

”是字母表中的有限个符号序列。因此，在你的问题中：“...无限长的字符串...“在形式语言中是无效的语句，因为字符串必须是有限的。

所以，当你说，你已经证明了M不是一个决策者，这意味着，你已经证明了M对于“至少一个Sigma-star字符串”是一个无限循环。此字符串可以在集合A或A-bar中。

我在这里的观点是，如果没有任何语言，你就不能证明一个TM本身就是决策者或非决策者。

现在，基于这个澄清，如果你得到了你的答案，那是很好的，但如果没有，你能不能重新表述你的问题更准确。