REクラスに属さない唯一の言語は対角言語ですが、残念ながらその補完言語は再帰的に列挙可能です。誰にもアイデアはありますか？
1 に答える
0
次のセットを考えてみましょう: なんらかの入力で停止しないすべてのマシン。つまり、M が入力 X で停止しないような入力 X が存在するすべてのマシン M です。特定のマシンが特定の入力で停止しないことを判断するアルゴリズム的な方法がないため、これは再帰的に列挙できません。つまり、どのようにしますか？入力で実行中のマシンをシミュレートしますか? どれだけの時間？
このセットを補完するものは次のとおりです。すべての入力で停止するすべてのマシン。つまり、任意の入力 X で常に停止するすべてのマシン M です。特定のマシンが可能なすべての入力で停止することを決定するアルゴリズム的な方法がないため、これも再帰的に列挙できません。どのようにしますか？それらをすべてチェックしますか？
于 2013-12-16T16:21:07.733 に答える