什麼是圖靈可識別的，我如何證明兩種語言的補充可以使用Co-Turing概念來判斷？

Question

設L1和L2是兩種語言，使得不存在屬於L1和L2的字符串w。 我在如何證明這個問題上掙扎，如果L1和L2都是圖靈可識別的，則存在一個可判定的語言A，使得L1⊆A和L2⊆A`。 A` - 的

Answer 1

補我們可以假設既不L1也不L2是可判定的，因爲如果是任一，溶液是微不足道的（讓如果A = L1或A' = L2L1或L2是可判定的，分別地）。尤其是，L1和L2都不是圖靈可識別的。

鑑於此，A必須等於集合L1並添加了一些元素（如果它是超集，它必須至少包含A1中的元素）。因爲L2是A'的子集，所以添加到L1以形成A的元素都可以在L2中。此外，我們必須添加無限多的項目，因爲添加有限的許多項目不能渲染A可確定，其中L1不是。

分手了的東西不L1或L2成兩種語言R1和R2使得這些語言沒有任何共同之處，每串是在L1，L2，R1和R2只有一個。此外，選擇R1和R2，這樣R1是圖靈可識別的，R2是圖靈可識別的，並且這兩個集合都是無限的。讓A = L1 U R1。現在，A' = L2 U R2。

1. A是共圖靈可識別的。如果w不在L1中，我們最終可以認識到這一事實。如果w不在R1中，我們可以決定這一事實。因此，我們終於可以認識到w既不在。

2. L2是c-Turing可識別的。如果w不在L2中，我們最終可以認識到這一事實。如果它不在L2中，則它在A或R2之間。但我們可以決定w是否在R2之內，因爲R2是可確定的。因此，如果我們認識到w不在L2並且決定它不在R2中，我們已經認識到w在A中。因此，A是圖靈可識別的。

3. 我們在1中看到，A是圖靈可識別的，而在2中，A是圖靈可識別的。因此，A是可確定的。因此，A'是可確定的。

請注意，我們有點揮手我們手中有在L1或L2當我們「分手」的東西沒有分成兩個無限的語言，一個共同圖靈機可識別和其他共同圖靈機可識別。似乎可以肯定的是，在任何無限語言中，都必須存在一種可識別但不可判定的語言的適當子集。您可能需要查看和/或單獨驗證。證明思想：任何無限集的元素都可以按字典順序排列，在這種情況下，字母表中所有字符串的語言都是雙向的;因爲在所有字符串集合中都有這樣的可識別但不可判定的語言，所以在這組字符串中也必須存在可識別但不可判定的語言。注意到（L1 U L2）'是可識別的，因爲可能需要嚴格地進行任何爭論。