是否存在一种不是图灵可识别的常规语言？

Question

正则语言有可能是非图灵可识别的吗？

Answer 1

不！如果你有一种常规语言，你可以获得它的 DFA，然后通过稍微调整转换将 DFA 转换为图灵机，以便它们机械地向前移动磁带头。因此，该语言也是图灵可识别的。