計算理論的歷史

導論篇

計算理論簡介

計算理論的歷史

可計算性

可計算性簡介

圖靈機

不可計算問題

遞歸可枚舉

不完備定理

複雜度

複雜度簡介

複雜度理論

NP-Complete

隨機複雜度

密碼學理論

趨近演算法

訊息

相關網站

參考文獻

最新修改

簡體版

English

簡介

在電腦出現之後,人們對電腦到底能做些甚麼感到相當好奇,於是有一批數學家在進行電腦研究時,以數學的手法探討電腦能力的極限問題,因而形成了一個介於電腦與數學之間的特殊領域,這個領域就是「計算理論」。

Alan Turing 是計算理論最重要的人物之一,目前有電腦界諾貝爾獎之稱的圖靈獎 (Turing Award),就是以他的名字命名的獎項,可見 Turing 在計算理論領域的地位。

希爾伯特 (David Hilbert)

事實上,在電腦被發明之前,數學界早已開始探索「公理系統」的能力極限。在西元 1900 年時,德國的偉大數學家希爾伯特 (Hilbert),提出了著名的 23 個數學問題,其中的第二個問題如下所示。

證明算術公理系統的無矛盾性 The compatibility of the arithmetical axioms.

在上述問題中,希爾伯特的意思是要如何證明算術公理系統的 Compatibility,Compatibility 這個詞意謂著必須具有「一致性」 (Consistency) 與「完備性」(Completeness)。

所謂的「一致性」,是指公理系統本身不會具有矛盾的現象。假如我們用 A 代表該公理系統,那麼 A 具有一致性就是 A 不可能導出兩個矛盾的結論,也就是 A => P 與 A=> -P 不可能同時成立。

所謂的「完備性」,是指所有合法的算式都是可以被証明或否証的,沒有任何一個算式可以逃出該公理系統的掌握範圍。

然而,希爾伯特耗盡了整個後半生,卻也無法證明整數公理系統的一致性與完備性。或許是造化弄人,這個任務竟然被希爾伯特的一位優秀學生 - 哥德爾 (Godel) 所解決了,或者應該說是否決了。

哥德爾 (Kurt Gödel)

哥德爾實際上證明了兩個定理,第一個是 1929 年提出的「哥德爾完備定理」(Gödel's Complete Theorem),第二個是 1931 年證明的「哥德爾不完備定理」(Gödel's Incomplete Theorem),這兩個定理看來似乎相當矛盾,但事實上不然,因為兩者所討論的是不同的公理系統,前者的焦點是「一階邏輯系統」(First Order Logic),而後者的焦點則是「具備整數運算體系的一階邏輯系統」。

哥德爾完備定理證明了下列數學陳述:

一階邏輯系統是一致且完備的

一致性代表一階邏輯系統不會具有矛盾的情況,而完備性則說明了一階邏輯當中的所有算式都可以被証明或否証。

哥德爾不完備定理證明了下列數學陳述:

任何一個相容的數學形式化理論中,只要它強到足以蘊涵皮亞諾算術公理,就可以在其中構造在體系中既不能證明也不能否證的命題。

哥德爾不完備定理改用另一個說法,如下所示:

如果一個(強度足以證明基本算術公理的)公理系統可以用來證明它自身的相容性,那麼它是不相容的。

圖靈 (Alan Turing, 1933) (Turing Machine)

圖靈是英國最早進入電腦領域的先驅者之一,他提出了著名的圖靈機電腦架構,這種架構在實務上很難使用,但是在理論上卻具有相當大的力量。圖靈提出該架構時正處於電腦發明的前期,電腦的理論開始建立,但真正的電腦則尚未被建構出來。當他思考圖靈機的能力極限時,發現了有些問題是圖靈機所不可能做到的,其中一個較著名的問題是「停止問題」(Halting Problem),他的証明方法有點類似哥德爾的方法,都可以說是「對角証法」的一個範例。

另外,圖靈除了發現有些問題是電腦所無法解決的之外,還曾在一篇稱為 Can A Machine Think? 的論文中,提出了一種用於判定機器是否具有智慧檢驗方法,該方法後來被稱為圖靈測試 (Turing Test)。

Kleene : (Recursive Function)

Church : (lambda-calculus)

羅賓遜 (John Alan Robinson)

雖然哥德爾證明了一階邏輯是完備的,但是卻沒有給出一個建構式的方法,可以推理出所有的的一階邏輯定理。這個問題由 John Alan Robinson 在 1965 年解決了。

Robinson 提出的 refutation 邏輯推論法是一種反證法,任何一階邏輯的算式 P 只要在系統 S 當中是真的,只要將 -P 加入該系統 S 中,就可以經由反證法導出矛盾。如果 P 在系統 S 當中不是真的,那麼將 P 加入 S 當中就無法導出矛盾。

所謂的 refutation 反證法是依靠一個稱為 resolution 的邏輯規則,該規則如下所示:

(1)
\begin{eqnarray} \frac{ a_1 | \ldots | a_i | \ldots | a_n \quad ; \quad b_1 | \ldots | -a_i | \ldots | b_m} {a_1 | \ldots | a_{i-1} | a_{i+1} | \ldots | a_n | b_1 | \ldots | b_{j-1} | b_{j+1} | \ldots | b_m} \end{eqnarray}

假如我們將上述算式中的 $a_1 | \ldots | a_{i-1} | a_{i+1} | \ldots | a_n$ 寫為 A,將 $b_1 | \ldots | b_{j-1} | b_{j+1} \ldots | b_m}$ 寫為 B,則上述算式可以改寫如下:

(2)
\begin{eqnarray} \frac{ A | a_i ; B | -a_i} {A | B} \end{eqnarray}

庫克 (Stephen Cook)

即便 Turing 已經證明了有些問題電腦是無法解決的,但是電腦仍然可以解決許多問題。但是在 1971 年,Stephen Cook 在一篇名為 「The complexity of theorem-proving procedures」的論文中,提出了一個計算理論上劃時代的方法,並且給出了一類稱為 NP-Complete 的問題。這類問題雖然電腦可能解決,但是直到現今為止,卻沒有任何一個問題可以在多項式時間內解決。

反過來說,NP-Complete 當中的問題,直到目前為止都只存在指數複雜度 $O(2^n)$ 的解決方案,因此這類問題都是電腦領域的難題,即使可以解決,電腦所花費的時間將會隨著輸入的長度而暴增,因此輸入較長的問題基本上也可以說是電腦無法解決的。

舉例而言,假如有個問題的複雜度是 $O(2^n)$ ,當輸入長度為 1000 時,電腦將會需要$O(2^1000)$ 的時間才能計算出該問題的解答。這基本上是不可能的,因為目前的電腦速度大約是 $2^10$,因此必須花上$2^{90}$ 秒,也就是大約 $1000^9$ 秒,這超過 $1000^6$ 年,也就是 1000000000000000000 年,這當然是無法容忍的時間。

但是,Cook 所提出的 NP-Complete 問題,最有趣的是在於他的未知性,因為沒有人知道這些問題是否有較快速的解法,這也是其定義中的 NP 這兩個字的玄機,Nondeterminism Polynomial (非確定性的多項式時間)。

從 1971 年以來,NP-Complete 就一直是資訊科學界最大的未解問題,沒有任何人能找到一個演算法可以在多項式時間內解答 NP-Complete 問題,或許未來也不會有人找到這樣的演算法,Stephen Cook 給了探索資訊科學理論的人一個極大的挑戰,或許就是為了等您來解答。

參考文獻

  1. 維基百科:希爾伯特的23個問題
  2. 維基百科:哥德爾不完備定理
  3. 維基百科:哥德爾完全性定理
  4. Hilbert's Mathematical Problems
  5. wikipedia:Turing
  6. wikipedia:Kurt_Gödel
  7. wikipedia:Hilterg's Problem
  8. John Alan Robinson
  9. Resolution (Logic)
  10. NP-Complete

Facebook

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License