在計算理論中，丘奇-圖靈論題是什麼？

丘奇-圖靈論題指出，每個可解的判定問題都可以轉化為一個等價的圖靈機問題。

它可以用以下兩種方式解釋：

• 判定問題的丘奇-圖靈論題。

• 判定問題的擴充套件丘奇-圖靈論題。

讓我們來了解這兩種方式。

判定問題的丘奇-圖靈論題

如果且僅當存在一個對於所有輸入字串都停止並解決問題的圖靈機時，才存在某種有效的程式來解決任何判定問題。

判定問題的擴充套件丘奇-圖靈論題

如果且僅當存在一個精確接受 Q 中答案為“是”的元素的圖靈機時，則稱判定問題 Q 是部分可解的。

證明

丘奇-圖靈論題的證明是一種在建立判定演算法的存在性時經常採用的捷徑。

對於任何判定問題，與其構建一個圖靈機解決方案，不如讓我們描述一個解決該問題的有效程式。

丘奇-圖靈論題說明，一個判定問題 Q 有解當且僅當存在一個圖靈機可以確定每個 q ϵ Q 的答案。如果不存在這樣的圖靈機，則稱該問題是不可判定的。

Bhanu Priya

更新於： 2021年6月12日

26K+ 瀏覽量

開啟你的職業生涯

透過完成課程獲得認證

開始學習