我从数学交换中找到了以下解释
一种语言是可识别的，如果有一个图灵机将停止并仅接受该语言中的字符串，并且对于不在该语言中的字符串，TM 要么拒绝，要么根本不停止。注意：没有要求图灵机应该为非该语言的字符串停止。
一种语言是可判定的，如果有一个图灵机将接受该语言中的字符串并拒绝该语言中的字符串。”
我真的看不出两者有什么区别。仅接受语言字符串的图灵机与接受语言字符串的图灵机有什么区别？这是否意味着任何图灵机都可以接受任何东西？
问问题
317 次
2 回答
0
不同之处在于 Decider（决定的 TM ）总是在任何输入（无论接受还是拒绝）上停止，而识别器除了停止之外可能永远循环。当它永远循环时，识别器只能在一些“永远”时间之后决定。这就是为什么我们称它为识别器而不是决定器，因为它有时无法决定。
于 2015-03-26T06:04:37.080 回答
0
我真的看不出两者有什么区别。
不同之处在于，对于Decidable语言，您可以构建一个始终能够区分有效和无效“话语”的编译器。相比之下，如果语言只是可识别的，则存在无效的“话语”，这将导致编译器进入无限循环。
请注意，通过用图灵机来表达这一点，他们谈论的是理论上可能的事情；即该语言的任何理论上可能的编译器，而不仅仅是特定的编译器。
并且语言“如果有一个图灵机......”意味着可以制定这样的车削机。它不是在谈论所有的图灵机。旨在（比如说）告诉您一个数字是否为奇数的图灵机显然不会充当语言识别器。
（如果您不明白为什么会这样，您需要对该主题进行更多背景阅读。我建议您从Wikipedia开始。）
于 2014-02-09T04:24:26.783 回答