什麼是 TOC 中的判定問題？

判定問題 Q 是一個問題的集合，每個問題都有一個 Yes 或 No 的答案。比如，“10 是一個完全平方數嗎？”。這是一個判定問題的例子。判定問題通常包含的都是一組無限關聯的問題。

示例

問題 PSQ 用於確定一個任意自然數是不是完全平方數，它有一些像下面這樣的值得懷疑的問題：

  • q0: 0 是完全平方數嗎？
  • q1: 1 是完全平方數嗎？
  • q2: 2 是完全平方數嗎？

解決方法

判定問題 Q 的解決方法是一個演算法，它可以確定每個問題 q ϵ Q 的近似答案。

解決判定問題的演算法必須是：

  • 完全的。
  • 機械的。
  • 確定的。

滿足上述所有屬性的程式通常被稱為有效的。

如果一個問題可以表示為一組從遞迴語言中接受的字串，那麼該問題就被稱為可判定問題。

因為確定性多軌多磁帶機計算可以在標準的圖靈機上模擬，所以使用這些機器的解法也可以確定問題的可判定性。

判定問題如下：

上次更新： 2021 年 6 月 12 日

2K+ 次瀏覽

開啟 職業生涯

完成課程認證

開始學習
廣告