資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究計算理論中的不可判定問題是什麼？
在計算理論 (TOC) 中，對於那些我們無法構建演算法，使其在無限時間內都能正確回答的問題，被稱為不可判定問題。
如果不存在圖靈機能夠始終在無限時間內停止並回答“是”或“否”，則該問題是不可判定的。
示例
下面解釋了不可判定問題的示例。這裡，CFG 指的是上下文無關文法。
兩個 CFG L 和 M 是否相等 - 由於我們無法確定任何 CFG 的所有字串，因此我們無法預測兩個 CFG 是否相等。
給定一個上下文無關語言，不存在圖靈機 (TM) 能夠始終在無限時間內停止並給出該語言是否模糊的答案。
給定兩個上下文無關語言，不存在圖靈機能夠始終在無限時間內停止並給出這兩個上下文無關語言是否相等的答案。
CFG 是否會生成輸入字母表 (∑*) 的所有可能字串是不可判定的。
停機問題
停機問題是不可判定問題中最著名的一個。
考慮以下程式碼
num=1;
while(num=0)
{
num=num+1;
}它會永遠迴圈計數，因為它永遠不會等於 0。這是一個停機問題的例子。
注意：每個上下文無關語言都是可判定的。
其他一些不可判定問題包括：
全域問題 - 確定任意 TM 是否在所有輸入上都停止。這等價於判斷一個程式對於任何輸入是否可能進入無限迴圈的問題。它與停機問題不同，停機問題詢問的是對於特定輸入程式是否進入無限迴圈。
等價問題 - 確定兩個 TM 是否接受相同的語言。這等價於判斷兩個程式是否對每個輸入都計算出相同的輸出的問題。
更新於： 2021年6月16日
12K+ 次瀏覽
廣告