超計算

超計算或超圖靈計算可以輸出非圖靈可計算結果的計算模型。

基本介紹

• 中文名：超計算
• 或稱：超圖靈計算

內容

例如，一台可以解決停機問題的機器可算作一台超計算機；可以正確推演皮亞諾算術中每一個狀態的機器亦然。

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

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

可計算函式

在可計算性理論中，可計算函式（computable function）或圖靈可計算函式是研究的基本對象。它們使我們直覺上的算法概念更加精確。使用可計算函式來討論可計算性而不提及任何具體的計算模型，如圖靈機或暫存器機。但是它們的定義必須提及某種特殊的計算模型。

在可計算函式的精確定義之前，數學家經常使用非正式術語可有效計算的。這個術語因此可以被認同為可計算函式。儘管這些函式被叫做有效的，它們可能極其困難。可行可計算性和計算複雜性研究可有效計算的函式。

依據邱奇-圖靈論題，可計算函式精確的是使用給出無限數量的時間和存儲空間的機器計算設備來計算的函式。等價的說，這個論題聲稱有算法的任何函式都是可計算的。

可以使用Blum公理來在可計算函式的集合上定義抽象計算複雜性理論。在計算複雜性理論中，確定一個可計算函式的複雜性的問題叫做功能性問題。

機率圖靈機

在計算複雜性理論內，機率圖靈機是一個非決定型圖靈機，在每個轉折點根據某種機率分布隨機選擇某種可行的轉變(transition)。

在轉變是均勻分布機率的例子裡面，我們可以定義為決定型圖靈機多了一個新增的"寫入"指令，這一個寫入指令的值是所有圖靈機能用符號的均勻分布機率選擇出的符號 (概括地說，這個寫入指令以相同的機率在紙帶上面寫入'1'或者'0'。) 另一個常用的定義是多了一條隨機紙帶，上面布滿了許多隨機位元值的確定型圖靈機。

所以，機率圖靈機可以有隨機的結果(與決定型圖靈機不同)；給定一個輸入和一個狀態機，機器運作的時間長度會不同，或者甚至不會停止； 甚至，這機器可能在這一次操作下回傳為接受，下一次相同的輸入值卻回傳為拒絕。

因此如何去理解被一個機率圖靈機接受字串的方式可以用許多不同的方式定義。 同時也有許多種因為我們對accept方式的不同，而產生了許多的多項式時間隨機複雜度類，包含了RP，Co-RP，BPPandZPP。 如果我們把多項式時間的限制改成對數空間的限制，我們則有了跟上面雷同的RL，Co-RL，BPL，和ZPL。如果我們同時限制兩者，則有了RLP，Co-RLP，BPLP，和ZPLP。

隨機計算對於定義大多數的互動式證明系統也是極為重要的，因為驗證者機器需要隨機性來避免被全能的證明者預測或者欺騙。 例如說，IP這個類別等同PSPACE，但是如果把驗證者的隨機性移除，我們就只有NP，一個一般而言相信(但尚未證明)是比起IP要小的複雜度類。

複雜度理論的其中一個重點問題是：是否隨機性增加了算法的能力？ 換句話說，是否有問題在多項式時間內可以以機率圖靈機解決但是不能以決定型圖靈機解決？或者是決定型圖靈機可以在至多只有多項式時間的變慢之下，完全的模仿隨機圖靈機的動作？現今的研究者大部分相信後者，這同時可以推出P=BPP。相同問題的對數空間(log space)版本(是否L=BPLP?)則比起多項式時間版本更被廣泛相信為真。另外，隨機性給予互動式證明系統的力量，以及對困難問題所能建立更簡單的算法的特質，例如多項式時間內的質數測試(primality testing)和對數空間的圖相連測試(graph connectedness testing)，又隱含著隨機性是有可能增加計算能力的。

量子計算機則是另一種先天就具有著機率性質的計算模式。