0

只有我想不到的、不属于 RE 类的语言是对角语言,但不幸的是,它的补充语言是递归可枚举的。有没有人有任何想法?

4

1 回答 1

0

考虑以下集合:所有无法在某些输入上停止的机器。换句话说,存在输入 X 的所有机器 M 使得 M 不会在输入 X 上停止。这不是递归可枚举的,因为没有算法方法可以确定给定机器无法在给定输入上停止。我的意思是,你会怎么做?模拟在输入上运行的机器?多长时间?

该集合的补充如下:在所有输入上停止的所有机器。换句话说,所有机器 M 总是在任何输入 X 上停止。这也不是递归可枚举的,因为没有算法方法来确定给定机器在所有可能的输入上停止。你会怎么做?全部检查?

于 2013-12-16T16:21:07.733 回答