computer-science - 常规、图灵可判定和图灵可识别是什么意思？

Question

我知道之前有人问过这个问题，但老实说，我并没有清楚地理解它。

我目前正在研究计算理论，我正在研究“证明一种语言是可判定的、可识别的或规则的”这样的术语。

用最简单的术语来说，它们实际上是什么意思，我们如何证明这些事情？

score 3 · Accepted Answer

我们正在谈论一种语言而不是 Alphabet ，这意味着(由由来自的字母组成的单词组成)。

可判定
意味着存在一个图灵机，它将对任何输入字停止并接受，对任何输入字停止并拒绝。

可识别
意味着存在一个图灵机，它会停止并接受任何输入单词并且停止或不停止（但不会停止并接受！）任何输入。

另请参阅MathExchange 上的可识别与可判定的区别。

正则
意味着可以通过正则表达式创建。重要的是要注意，理论计算机科学中的这些正则表达式与 PERL 或 Java 等编程语言中已知的 RegEx 功能不同。事实上，这些正则表达式确实比正则表达式更强大（不知道这是否是正确的英文术语）。

这里给出了正则表达式的一个很好的定义：

对于一个字母

没有别的东西是正则表达式。

我们如何证明这样的事情？

为了证明可判定性或可识别性，提供具有所需属性的图灵机通常是最容易的。由于Church-Turing 论文，任何编程语言都像图灵机一样强大。因此，在我的课程中，以编程语言或伪代码提供算法是完全可以接受的。

请注意，任何可识别的语言也是可识别的（但不是相反）。

为了证明正则性，大多数时候只提供一个构造语言的正则表达式是最简单的。有时需要证明正则表达式确实构造了，这通常不是太难（通常很明显）。

在许多讲座中，有一个关于正则表达式的约定，它允许更直观、更短（但不是更强大）的语法。

知道正则语言正是有限自动机可以识别的语言可能会很有趣。请注意，任何常规语言也是可判定的（因此是可识别的）。

为了反驳正则性，我只想提一下正则语言的抽引引理。