0

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

4

1 回答 1

0

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

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

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