檢查是否2種語言的圖靈識別或共同圖靈識別

Question

我有這2種語言

A = {<M> | M is a TM and L(M) contains exactly n strings } 
B = {<N> | N is a TM and L(N) contains more than n strings } 

我相信，這些2是不可判定的，但我不知道他們是否圖靈識別或共同圖靈識別。

Answer 1

B是圖靈可識別的，因爲我們可以在所有可能的輸入磁帶上交錯執行M。如果多於n的運行實例M曾經停止接受，則暫停接受。

我們知道A不能圖靈機可識別，因爲，如果它是，語言B' = {<N> | N is a TM and L(N) contains no more than n strings }是圖靈機可識別（我們可以交錯識別的執行1，2，...，n和制止，如果接受任何那些）。這意味着B和B'都是可確定的，因爲B'必須是圖靈可識別的。

如果A是共同圖靈識別的，我們可以識別接受多個不同於n的字符串的機器。特別要讓n = 1。我們可以運行識別器來識別機器，這些機器的語言包含n字符串以外的字符串，構造爲接受L(M) \ {w}，用於每個可能的字符串w。在每個階段，我們運行所有現有機器的一個步驟，然後構建一個新機器並重復，從而交錯執行，並確保所有TM最終都能夠運行任意多個步驟。

假設|L(M)| = 1，這些TM中只有一個TM將停止接受（除去L(M)中唯一的字符串），其餘的將暫停或永遠運行。因此，|L(M)| != 1的識別器可用於構造|L(M)| = 1的識別器。這通過減去所有可能的k輸入字符串集合到|L(M)| != k和|L(M)| = k。因此，如果A是共同圖靈識別的，那麼它也可以是圖靈識別的，因此可以確定。我們已經知道這是錯誤的，所以我們必須得出結論：A不是圖靈可識別的;它也不是圖靈可識別的。