遞歸和遞歸枚舉語言有什麼區別

Question

我想知道遞歸和遞歸枚舉語言在停止和圖靈機方面有什麼區別。我知道遞歸可枚舉語言是遞歸語言的子集，但我不確定這種差異。

Answer 1

您有R和之間RE向後的關係：- [R是RE的（適當的）子集。基本上，遞歸語言就是你總有一個決定因素。

回想一下遞歸可枚舉語言的定義：部分決定器存在;也就是說，一個圖靈機可以根據你的語言正確地接受/拒絕這個詞，或者如果這個詞不是你的語言，它可能會永遠循環。

相反，遞歸語言是一個總決定器存在的一種語言，即永遠不會循環的一種語言，並且總是停止在接受狀態或拒絕狀態。

把這兩個定義放在一起，顯然遞歸語言也是遞歸枚舉的，因爲總決策者也是部分決定者（它從來沒有「選擇」循環而不是停止正確答案）。