什麼是計算理論 (TOC) 中的可判定性？

在計算理論 (TOC) 中，有兩種型別的語言：

  • 可判定語言

  • 不可判定語言

如果一個問題存在解，並且可以構造相應的演算法，則稱該問題為可判定問題。

可判定問題的例子

找出1到50之間所有奇數。

對於這個問題，我們可以很容易地透過構造演算法找到解決方案。就圖靈機 (TM) 而言，如果一個問題是可判定的，那麼圖靈機無論是否接受其輸入都會停機。

就有限自動機 (FA) 而言，“可判定”指的是測試確定性有限自動機 (DFA) 是否接受輸入字串的問題。可判定語言對應於演算法可解的判定問題。

可判定性定理

在 Σ 上的語言 L 被稱為可判定的，如果：

  • 存在一個接受語言 L 的圖靈機 M

  • 對於所有 w ∈ Σ*，M 都會停機

可判定性

對於遞迴語言

  • 如果存在一個圖靈機能夠接受 L 中的所有字串並拒絕 L 之外的所有字串，則稱語言“L”為遞迴語言。

  • 圖靈機每次都會停機，併為每一個輸入給出接受或拒絕的答案。

遞迴可列舉語言：

  • 如果存在一個圖靈機能夠接受 L 中的所有輸入並停機，則稱語言“L”為遞迴可列舉語言。

  • 但對於不在 L 中的輸入，可能停機也可能不停機。

如果語言‘L’是遞迴語言，則它是可判定的。

所有可判定語言都是遞迴語言，反之亦然。

下圖解釋了可判定語言：

更新於：2021年6月14日

瀏覽量 10K+

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告