什麼是遞迴語言和遞迴可列舉語言？

在學習計算理論 (TOC) 中的遞迴可列舉語言之前，讓我們先了解遞迴語言的概念。

遞迴語言

如果語言 L 是某個圖靈機 (TM) 接受的字串集合，並且該圖靈機在所有輸入上都會停止執行，則語言 L 是遞迴的（可判定的）。

示例

當圖靈機到達最終狀態時，它會停止執行。我們也可以說，當圖靈機 M 達到狀態 q 以及要掃描的當前符號“a”，並且 δ(q, a) 未定義時，M 會停止執行。

有些圖靈機在某些輸入上永遠不會停止執行，因此我們需要區分由在所有輸入字串上都停止執行的圖靈機接受的語言和由在某些輸入字串上永遠不會停止執行的圖靈機接受的語言。

遞迴可列舉語言

如果語言 L 是某個 TM 接受的字串集合，則語言 L 是遞迴可列舉的。

如果 L 是遞迴可列舉語言，則：

如果 w ∈ L，則 TM 會在最終狀態停止執行；

如果 w ∉ L，則 TM 會在非最終狀態停止執行或永遠迴圈。

如果 L 是遞迴語言，則：

如果 w ∈ L，則 TM 會在最終狀態停止執行；

如果 w ∉ L，則 TM 會在非最終狀態停止執行。

遞迴語言也是遞迴可列舉的

證明 - 如果 L 是遞迴的，則存在一個 TM 可以判定語言中的成員，則：

  • 如果 x 屬於語言 L，則 M 接受 x。

  • 如果 x 不屬於語言 L，則 M 拒絕 x。

根據定義，M 可以識別那些被接受的字串。

更新於：2021年6月16日

27K+ 次瀏覽

啟動您的 職業生涯

完成課程獲得認證

開始學習
廣告