設L1和L2是兩種語言,使得不存在屬於L1和L2的字符串w。 我在如何證明這個問題上掙扎,如果L1和L2都是圖靈可識別的,則存在一個可判定的語言A,使得L1⊆A和L2⊆A`。 A` - 的什麼是圖靈可識別的,我如何證明兩種語言的補充可以使用Co-Turing概念來判斷?
回答
補我們可以假設既不L1
也不L2
是可判定的,因爲如果是任一,溶液是微不足道的(讓如果A = L1
或A' = L2
L1
或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
。
A
是共圖靈可識別的。如果w
不在L1
中,我們最終可以認識到這一事實。如果w
不在R1
中,我們可以決定這一事實。因此,我們終於可以認識到w
既不在。L2
是c-Turing可識別的。如果w
不在L2
中,我們最終可以認識到這一事實。如果它不在L2
中,則它在A
或R2
之間。但我們可以決定w
是否在R2
之內,因爲R2
是可確定的。因此,如果我們認識到w
不在L2
並且決定它不在R2
中,我們已經認識到w
在A
中。因此,A
是圖靈可識別的。我們在1中看到,
A
是圖靈可識別的,而在2中,A
是圖靈可識別的。因此,A
是可確定的。因此,A'
是可確定的。
請注意,我們有點揮手我們手中有在L1
或L2
當我們「分手」的東西沒有分成兩個無限的語言,一個共同圖靈機可識別和其他共同圖靈機可識別。似乎可以肯定的是,在任何無限語言中,都必須存在一種可識別但不可判定的語言的適當子集。您可能需要查看和/或單獨驗證。證明思想:任何無限集的元素都可以按字典順序排列,在這種情況下,字母表中所有字符串的語言都是雙向的;因爲在所有字符串集合中都有這樣的可識別但不可判定的語言,所以在這組字符串中也必須存在可識別但不可判定的語言。注意到(L1 U L2)'是可識別的,因爲可能需要嚴格地進行任何爭論。
- 1. 圖靈可識別語言是否可判定?
- 2. 證明這個語言是否可判定和識別
- 3. 當你證明一種語言是可判定的時,你在做什麼?
- 4. DFA可以識別多少種語言?
- 5. 任何人都可以爲我識別這種語言嗎?
- 6. CFG是否使用可判斷的nil語言?
- 7. 語音識別的可用語言
- 8. 如何判斷一種語言是否是一見鍾情的?
- 9. 如何使用jQuery來判斷用戶是否可以滾動?
- 10. 任何人都可以識別這種編程語言?
- 11. 兩種語言的交集是什麼?
- 12. 什麼是可以編譯的最高級別的語言?
- 13. 我可以通過Android以外的語言獲得語言識別嗎?
- 14. CNTKTextFormatDeserializer的概念是什麼以及爲什麼使用?
- 15. 什麼是概念?
- 16. Rest Assured可以使用什麼語言
- 17. ANCS:PositiveAction的概念是什麼?
- 18. Kotlin意圖的概念是什麼?
- 19. 如何識別輸入字符串具有可變的判斷
- 20. Subversion中的Head的概念是什麼以及Trunk的區別是什麼
- 21. 爲什麼Ture可識別語言的類在Complement中關閉?
- 22. 多種語言的Vista語音識別
- 23. 各種語言的關鍵編程概念和術語
- 24. 「幻數」的概念是否從語言變爲語言?
- 25. 我可以使用多種語言的基於Linux的ORM嗎?
- 26. 我可以使用什麼算法來識別網頁上的內容
- 27. 我可以使用Twist概念的參數嗎?
- 28. 多語言Sitecore 6網頁可以爲每種語言使用別名嗎?
- 29. 爲什麼不遞歸可枚舉語言不可判定
- 30. 我可以同時使用多種語言的OpenGL嗎?