講演 補充

 

思考可以由機器代勞嗎？（以及編碼的威力）

數數、進位法、算盤

帕斯卡齒輪算稅機

織布機

巴貝奇差分引擎、分析引擎（拉芙蕾斯程式語言）

自動算術（齒輪與電子）

做數學定理證明

 

 

 

「判定問題」

「通用步驟(演算法)問題」

公設是像下棋那樣的規則嗎？

非歐幾何公設跟歐氏幾何公設不同，我們怎知道非歐幾何的公設會不會導致矛盾？(consistent 前後一致的)，

希爾伯特證明了如果「算術」是前後一致的，「歐氏幾何」也會是。而另有人證明如果「歐氏幾何」公設是 consistent ，則「非歐幾何」公設也是 consistent。 這樣固然是不錯，如果不必環環相依總是更好。

他因此認為數學的公設基礎應該具備以下兩個 (理所當然的) 持性：

(1) 公設應具前後一致性：不含矛盾

(2) 公設應具完備性：任何陳述在公設的規律法則下， 皆可被證明為真或偽。（

希爾伯特心中的 Program，認為公設體系就是建立成滿足上述兩個 "理所當然" 的條件 (1920)。也因此，他意識到有另一個需要 (1928)，即加入了「判定問題」 (Entscheidungsprogram)： 要有一個 (通用的) 判斷流程步驟來告訴我們一個數學陳述能不能用現有的公設證明。他本人相信這樣的流程存在，而 Entscheidungsprogram 則意指「如何找出」這個通用步驟流程。

（有了它，就可以打造數學陳述真偽判定機，它將是定理證明機的第一步）

 

也就是說，希爾伯特 (Hilbert) (代表當時的數學界主流) 原本期待新世紀重要的大挑戰，其中一個便是：

一個通用的演算法，能對 (合適) 公理下的任何數學陳述，證明為真或偽。

但哥德爾證明了，一致性的公設數學體糸是不完備 (incomplete) 的，也就是說，給定公設下，存在既無法證明為真、也沒有法證明為偽的陳述。這個公設體系被新發現的本質，震撼了數學界，哥德爾也被視為等同愛因斯坦的世紀大學者。

 

「判定問題」

在「不存在一個通用的演算法，能對公理下的任何數學陳，證明為真或偽」的失望前提下，退而求其次，仍剩下「判定問題」這個重要而有趣的提問。

Chuch 最先證明判定問題不用問，無法實現，是個假議題。 Turing 只稍晚一點，但提出完全不同的方法，然後自已再證明兩者等效。

判定可證

某個問題屬「可判定」，乃指可找到一個步驟，對該問題的所有情況，

「不可判定」

不管什麼

一般而言，要證明一個問題是

「判定問題」

我們將看到

 

什麼

 

己知無法判定的「判定問題」

例一：希爾伯持第十問題

丟番圖公式，如 x2 + y2 = z2、x3 + y3 = z3 等有沒有的整數解，有或無的判定

 

例二：Post 的對應問題

標籤牌

任給定一組(套) 上下有字的 標籤牌，牌可重覆用，問排出上下行文字列一模一樣，能成功或不能成功的判定問題

 

例三：停機問題

用一個演算法去檢查另一個演算法讀入某筆輸入的情況下，會不會完成 (程式結束運作) 而給出，會結束完成或是陷入無窮沒完沒了的判定問題

 

有限自動機（相當於電子計算機）

有一組內部規則，按輸入的指令照作

 

圖靈機（相當於電腦）

有內部規則，並讀/寫頭、能在紙帶格上按狀態/規則移動，讀入及寫入覆蓋

 

判定 / 判定問題 的 步驟 (聞香一下)

給一串左右括號所排出的字串，判定是否套疊正確

) ( ) (

( ( ) )

 

圖靈大論文

考量無限、允許無限

定義可計算數：基於程式，以及輸入，可故產生出來的實數

可計算數的無限等級是「可數的」( 即 Aleph 0 )

可計算數是可數的

如果存在通用演算法可判定圖靈機處理圖靈，將導致 阿勒夫等級(無限性程度) 矛盾

因此，「判定問題」要找的真偽判定的通用演算法不存在，是假議題

不是最

 

貢獻

圖靈機極為簡單，卻己經建立的通用計算機器的架構