爲什麼不遞歸可枚舉語言不可判定

Question

這是可判定的定義，維基百科

在可計算性理論，一個不可判定問題由針對特定是/不需要回答情況的家庭 的，例如 ，在給定任何問題實例爲 輸入的情況下，沒有計算機程序，終止並在有限的 步數之後輸出所需的答案。更正式地說，一個不可判定的問題是一個問題 其語言不是遞歸集

的遞歸集是遞歸可枚舉一個子集。遞歸集外有一些遞歸可枚舉的語言。那麼爲什麼不是遞歸可枚舉語言不可判定？

Answer 1

遞歸可枚舉的語言/集合也被稱爲半可判定的。它們不是可判定的，因爲沒有一臺機器會查看輸入並且說「是」或「否」（正確）。半決定意味着你可以編寫一個機器來查看輸入，並且如果輸入是在集合中則爲是，或者如果輸入不在集合中則停止。 半可判定原來是相當於遞歸可枚舉以同樣的方式，可判定相當於遞歸： -

如果你有一個枚舉遞歸可枚舉語言圖靈機R，你可以製作一臺新的機器D，它接受可能或不可能在語言/設置中的輸入。 D運行R直到R輸出該集合的第一個元素，然後D將其與其輸入進行比較。如果它們匹配，則返回「是」結果。如果它們不匹配，它會繼續運行R直到它獲得下一個元素，依此類推。由於R從不停止（因爲語言只能遞歸枚舉，而不是遞歸），所以D會回答是或不停止。相反，如果您有一臺圖靈機D可以回答是或不能停機，那麼您可以製作一臺新機器R，它使用通常的技術通過不同的輸入一次一步地運行多個D實例：所有可能或可能不在集合中的元素。每次D的並行執行中止並回答「是」時，R輸出D的輸入，並在所有其餘輸入上繼續執行D. R永遠不會停止（因爲有一些D不會停止的輸入），但最終它會輸出D回答「是」的每個元素，即集合/語言中的每個元素。

不要因爲認爲存在三種（不相交）的集合而感到困惑：可判定的，半可判定的和不可判定的。有兩種：可判定和不可判定。所有可判定的集合也是半可判定的（儘管這樣說非常不尋常）。一些不可判定的集合也是半可判定的。這與說所有可枚舉集合都是遞歸可枚舉，以及一​​些不可枚舉集合是遞歸可枚舉相同。

Answer 2

甲semidecidable問題（或等價一個遞歸可枚舉的問題）可以是：

1. 可判定：如果問題及其補均爲semidecidable（或遞歸可枚舉的），則該問題是可判定的（遞歸）。

2. 不可確定：如果問題是semidecidable和它的補碼是semidecidable（即，不是遞歸可枚舉）。

重要提示：請記住，一個可判定（遞歸）問題也semidecidable（遞歸可枚舉）。相反，如果一個問題不是遞歸可枚舉的（semidecidable），那麼不是遞歸的（可判定的）。

什麼維基詞條中說的是：

部分可判定問題是不可判定被稱爲 判定的。

一般來說，半判定問題（遞歸可枚舉）可以是可判定的（遞歸的）或不可判定的（非遞歸可枚舉的）。

另請注意問題及其補充可能（或只是其中之一）甚至不可半決定（非遞歸可枚舉）。還要注意，如果問題是遞歸的，則它的補碼也是遞歸的。

Answer 3

我相信一組問題的圖形表示在這裏可能會更有幫助（這裏不同集合的大小沒有意義）。

總結：

1. 每一個可判定的（遞歸）問題也是半可判定（遞歸可枚舉）。
2. 不可判定（遞歸）的每個半可判定（遞歸枚舉）問題都是不可判定的。
3. 有不可判定的問題，不是半決定性的（遞歸枚舉）。