enumerable - 非正则语言的补语总是递归语言吗？

Question

非正则语言的补语总是递归语言吗？

我了解 1.context-free 语言不会在补语下关闭。2.递归可枚举语言在补码下不封闭。3.递归语言确实在补码下封闭。

但是我怎样才能使用这些事实来回答最初的问题呢？如何判断非正则语言是否递归？

Answer 1

不，非常规语言的补语并不总是递归的。一个反例是停止问题，其补码（所有不停止的程序）是非常规的。因此，停止问题本身不是递归的（而是递归可枚举的）是非常规语言的补充。（我认为提到的事实不会帮助你解决这个问题。）

一般来说，如果你想证明一个问题不是递归的，你必须将非递归语言（例如停机问题）简化为它。如果你想证明它是递归的，你必须证明有一个图灵机决定它（接受它并在每个输入时停止）。