資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究證明遞迴語言在反轉運算下是封閉的？
考慮一個在字母表 T 上的語言 L，如果存在一個圖靈機 (TM) 生成一個數字序列 T*，並且該序列恰好包含 L 的所有成員，則稱該語言為遞迴可列舉的。
而 L 被稱為遞迴的，如果存在一個圖靈機列出 L 的所有成員，並在每個成員作為輸入時停止。
因此，從以上陳述可以清楚地看出，每個遞迴語言也是遞迴可列舉的，但反之則不成立。
語言家族之間精確的關係如下所示。
定理
步驟 1 - 在字母表 T 上，一個語言 L 被稱為遞迴的，當且僅當 L 及其相對於 T* 的補集 L 都是遞迴可列舉的。
步驟 2 - 語言 L 的反轉 L^(R) 是 T* 中所有元素的字串的集合，我們可以透過將 L 中所有元素按反序排列得到。
步驟 3 - 讓我們考慮一個遞迴可列舉的語言 L，其所有元素都由圖靈機 M 列出。
步驟 4 - 現在我們可以設計另一個圖靈機 M'，其接受的字串是 L 中成員的反轉字串。
步驟 5 - 這也符合丘奇-圖靈論題，該論題指出每個有效的計算過程也可以由一些圖靈機完成。
步驟 6 - 現在，從以上討論可以清楚地看出，如果 L 是遞迴可列舉的，那麼其反轉 L^(R) 也是遞迴可列舉的。
步驟 7 - 如果 T* 中的字串 X 屬於 (L^(R))'，當且僅當 X 不屬於 L^(R)，這顯然意味著當且僅當 X^(R) 的反轉不屬於 L，這進一步意味著 X^(R) 屬於 L' ⇔ X 屬於 l^(R)。
即 (L^(R))' = L'^(R)
結論
如果 L 是遞迴的，則 L'(R) 及其補集 (L^(R))' 也是遞迴可列舉的，這進一步意味著 L^(R) 的反轉也是遞迴的。
更新於： 2021年6月16日
630 次瀏覽
廣告