非常规语言的补充是递归语言吗？

Question

非常规语言的补充是递归语言吗？

我明白， 1.无条件语言不补充关闭。 2.递归可枚举语言不补充。 3.递归语言确实是在补充下关闭的。

但是，如何使用这些事实回答最初的问题？如何判断一个非常规语言是否递归？

Answer 1

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

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