由淡入濃—如是我觀涂靈形象

計算複雜度

涂靈在普林斯頓近兩年的時間裡,名義上丘奇指導他完成一篇博士論文。其實從後見之明,我們知道涂靈在抵達普林斯頓之前,就已經作出比丘奇更深遠的貢獻。所以他們倆並不像一般博士班師徒間的關係,涂靈不僅沒有從丘奇那裡得到很多有用的思想,甚至他的博士論文因為遷就丘奇的偏好,不得不採取蘭布達符號系統,長度因而增加,並且削弱了涂靈原來更近直觀的風格。這篇名為“Systems of logic based on ordinals”(以下簡稱〈系統〉)的博士論文發表後,比〈論數〉更缺乏讀者。

〈系統〉想在哥德爾不完備定理破滅了數學整體機械化的夢想之後,重新檢討如果適度地用直觀輔助機械化,數學體系還能走到什麼程度。涂靈在他原有的機器模式裡,再加上一個有問必答的元件,他稱之為oracle,我們暫且譯為「玄器」。當機器按照涂靈機的指令運算到某個階段時,它需要知道某個問題的答案為「是」或「否」時,玄器即刻給出正確的答案。這個步驟在涂靈機的指令裡無法預先設計,因此它相當於運用「直觀」的一次跳躍。

因為涂靈機給予了極富啟示性的思想圖像,使得加入玄器也變得十分自然。另一位與涂靈同時代的美國邏輯學先驅波斯特(Emil Post, 1897~1954),迅速掌握到玄器的重要意義。當我們用涂靈機計算A 函數時,如果把B 函數的值當作玄器,就表示計算A的難度不會超過計算B的難度。所有只用涂靈機而不需要任何玄器協助就能計算的函數,就構成了難度最低的所謂的可計算函數(也稱為遞迴函數)。波斯特用裝備玄器的涂靈機來區分計算函數時相對的難度,從此開創了計算複雜度(computational complexity)理論的研究。

涂靈機儲存資料的紙帶,以及運算過程中所耗費的步驟數與方格數,很容易啟發人們考慮到計算時使用的時間與空間資源。要使計算在現實世界裡可行,這些資源的消耗必須加以合宜的限制。受不可計算世界裡複雜度研究的影響,在可計算的世界裡也可用消耗資源的多寡來區分相對難易程度。1971 年加拿大邏輯學家庫克(Stephen Cook, 1939~)引入了P 與NP兩種問題類。粗略地講, P 裡的問題都有快速的計算方法,而NP裡的問題到目前為止都還沒找到快速的計算方法。庫克還證明有一些在NP裡的問題如果一旦有快速的計算方法,則所有NP裡的問題都可以有快速的計算方法,這些問題稱為NP完備問題。P與NP到底是不是相異的兩類,已經成為克雷(Clay)數學研究所懸賞百萬美元的矚目問題之一。

下一頁  Pages: 1 2 3 4 5 6

123123123123123

123123123

123123

12222222222

Today is Monday.

I'm testing out a new plugin.


關於作者

Avatar

非營利性質的《科學月刊》創刊於1970年,自創刊以來始終致力於科學普及工作;我們相信,提供一份正確而完整的科學知識,就是回饋給讀者最好的品質保證。

網站更新隱私權聲明
本網站使用 cookie 及其他相關技術分析以確保使用者獲得最佳體驗,通過我們的網站,您確認並同意本網站的隱私權政策更新,了解最新隱私權政策