跳至內容

超計算

維基百科,自由的百科全書

超計算超圖靈計算可以輸出非圖靈可計算結果的計算模型。例如,一台可以解決停機問題的機器可算作一台超計算機;可以正確推演皮亞諾算術中每一個狀態的機器亦然。

邱奇-圖靈論題指出,任何可以用有限算法以紙筆計算的"可有效計算"函數都能被圖靈機計算。超計算機能計算圖靈機無法計算、即邱奇-圖靈論題中不可計算的的函數。

嚴格說來概率圖靈機的輸出是不可計算的。然而,大多數超計算方向的文獻更關注有用的計算而非隨機、不可計算的函數。

擴展閱讀

[編輯]

外部連結

[編輯]