通識週性別平等展 演講 (2021.03.26)

艾倫 圖靈：蘋果咬一口向他致敬

淡江大學 物理系 李明憲

 

 

 

 

致敬英雄？不置可否

 

 

 

 

 

 

 

 

 

 

 

世紀懸案、悲劇天才

自殺派

 

意外派

 

 

道歉赦免、撫平傷痛

受到幾十萬人請願的壓力，2009b英國政府作出道歉，2013 女玉赦免。

 

 

 

人的價值，超越性別

 

 

公設算學、千年傳承

歐基里德 (Euclid) 「幾何原本」"Elements"

古希臘數學家歐幾里得的《幾何原本》提出了五條公設。頭四條公設分別為：

(1) 由任意一點到任意一點可作直線。
(2) 一條有限直線可以繼續延長。
(3) 以任意點為心及任意的距離可以畫圓。
(4) 凡直角都相等。
(5) 同一平面內一條直線和另外兩條直線相交，若在某一側的兩個內角的和小於兩直角，則這兩直線經無限延長後在這一側相交。

 

牛頓進入劍橋後，也要讀 ( 拉丁文的) 《幾何原本》

 

 

環環相扣、齒輪帶動

人數的智慧能透過建造適當的機器來替代，省體力、省時間、甚至腦力。

數數（音：鼠樹）與進位數的不同

機器可以作為算術的輔助工具（圖一、圖二 ）

帕斯卡的孝心

巴貝奇 (Chales Barbedge))

愛達 - 拉芙蕾斯 (Ada Lovelase)

 

「算術」可以，「證明」如何？

 

 

世紀問題、大師提出

大數學家 Hilbert 在進入二十世紀 (1900) 提出了他認為最重要的 23 個問題。

公設體系的(一致性與)「完備性」

 

「判定」

 

判定問題 ( Entscheidungsproblem )

"存在一個運算流程，能判定任何陳述是假是真嗎？"

 

Newman 向圖靈介紹哥德爾的進展

 

補充說明（2021.05.06）

 

邏輯打底，嚴密構築

羅素、懷海德兩人的巨著「數學原理」，密密麻麻到 300 頁才證明 1 + 1 = 2 ，這是怎麼回事？

定義(自然)數字

符號化，並且希望符號能拼接在一起成為可推演腳本。

（水牛怎麼回答算術題？）


因為編碼，所以全能

突破工具的單一性：「編碼」讓萬用機器成為可能

 

 

有限自動機

 

圖靈機

 

編碼題例

 

 

 

所以「通用圖靈機」，想必超複雜吧？

非也，它(機器)傻瓜、你(程式)聰明，就好了啊。（電腦是要給你答案的，不是給你雞腿，能有多難？哈哈！）

 

說到簡單，來看另一種 ，有限自動機 Rule 110 的內部狀態，己經被證明是夠用於通用圖靈機 (Universal Turing Machine) (也有人翻譯萬用) ，

叫 110 的原因是，它針對 (7, 6, 5, 4, 3, 2, 1) 八種不同情況的輸入，分別給出 (0, 1, 1, 0, 1, 1, 1, 0) 這個清單列表的結果，而以二進位排入 這八個二元數，01101110two，26 + 25 + 23 + 22 + 21 = 64 + 32 + 8 + 4 + 2 = 110ten

 

（事實上，圖靈證明六個 primitive 便足以建構萬用機的所有動作：左、右、讀、寫、掃描、無作為。）

 

這麼簡單？！那為什麼還要台積電的啥米 "七奈米"、"五奈米"？

因為機器簡單，程式的部份就會超、超、超龐大複雜的，反而沒效率。

現代的電腦，內部有特化的線路，以極高時脈去作常用的運算操作，例如加法。

即便如此，「複雜指令集」(如 x86) 與「精簡指令集」(如 ARM) 兩大陣營的電腦晶片架構同時在市場上存在

 

 

證明「通用判定演算法」假想根本是不可能的

 

 

人想像得到，但是機械永遠做不到的例子

(出一支嘴比較容易)

 

不可計算數的例子

最大偏移函數 (Maximum Shift Function) S(n)，（是有名 Busy Beaver Function 的一種最簡單的版本）

n 態 (接受態與拒絕態不算) 的所有可能圖靈機，從空白紙帶 開始， 會停止的，最多 幾步會停 ，步數就是 S(n)

S(1) = 1

S(2) = 6

S(3) = 21

S(4) = 107

以上為己知

S(5) > or = 47,176,870

S(6) > 7.4 × 1036534

 

N = Σn=1∞ [1/ 10S(n)]

 

在無限的旅程上相遇？

自然數分奇偶，所以正偶數比正整數少，對嗎？

希爾伯特的旅館

定義無限等級的方法：1-1 對應

Cantor 提出，他尊敬的老師 Kronecker 暴怒反對，斥為根本不是數學的異端邪說，Cantor ，受精神打 擊很大，幾次發瘋入院。

Hilbert 卻「不願被逐出 Cantor 建造的樂園」

有理數與實數是不同等級 cardinal number

 

「計算」的 cardinality

因為編碼結構的樣子，機器加數據的編碼 1-1 對應到自然數，無限性等級 Aleph 0

 

定義可計算數：

實數，給圖靈機一個輸入，它會(不斷)印出位數包含小數點值

 

可計算數 (K) 是可數的

我們現在要證明 | K | = aleph_0，

首先 | K | <= Aleph0

為什麼？因為根據定義，每個可計算數都來自圖靈機配上某個輸入，根據編碼，將會被寫成某一個

110101110010110101 ..... 011000011101

因此它會與某個自然數等值而形成唯一的對應，K ⊂ N ，故 | K | <= Aleph0

 

另外，K 包含 Q 所以 Aleph_0 = | Q | <= | K |

綜合以上，Aleph_0 <= | K | <= Aleph_0

| K | = Aleph_0 ，得證。

 

 

不是所有可計算數，都可被有效地求值得出

（由 Turing 加以證明，此結果將會被用最後在「判定問題」的反證上）

反證法 ，若有 則 0 ~ 1 間的列出如下

用 4 或 5 去換 aii ，冒出沒被表列，但卻是圖靈機做得出的 數，矛盾！

（避開用 0 與 9 因為無限小數 0.999999... = 1）

 

圖靈機的限制（也是所有電腦 / 演算法 的限制）

1. 隨內容複雜度提高，步步走的方法，在可運用的時間內得不到結果。

2. 有些問題靠演算法是無法判定有無答案的。

 

「判定問題」的反證

能同時處理「機器」與「輸入」（因為編碼的新想法）的圖靈機，帶來了一個豐富而有趣的特性，就是幫忙找到了一類新的數字，叫做「可計算數」。這個類別是因為圖靈機的定義才分類出來的，而可計算數裡面卻存在著圖靈機也就是演算法永遠也沒有辦法觸及的部分。圖靈就是用這一個點，來反正歷史上有名的「判定問題」。他找到一個用演算法處理也沒有辦法找到的物件，而這個物件是真實存在的。那當然就不存在某個演算法可以判定任何數學陳述真偽性。

換句話說，每一個機器編碼並上1組數據，就對應到1個自然數。這樣的話，各種可能的機器，配上各種可能的輸入數據，就構成了可計算數的全體。而判定問題所要求的，卻確是一個單一的機器或者是演算流程方法，能夠判定所有的乘數，那這就做不到了。集眾多機器的可能性所構建出來的大全體，沒有辦法簡單的被以單一機器/單一演算法配合任何的數據來涵蓋。這就是圖靈機用來反證「判定問題」的核心觀點。

 

密碼之戰、扮演要角

Egnima 密碼機

波蘭數學家己有大成功，拆解密碼機的構造，利用群論（探討對稱性的數學）將可能性簡化，並利用複製的多台密碼機

趕在波蘭被德軍佔領之前，

 

 

演算理論、奠基偉業

皮亞諾公設

 

λ-計算法

自然數

 

由於圖靈機

 

 

 

思考智慧、判別智能

「圖靈測試」（別人後來取的，圖靈自己把它叫作「模仿遊戲」(Imitation Game) ）人工智慧領域歷久彌新的經典問題。

 

問：電腦能思考嗎？

愛達-拉芙蕾斯也回答過這個問題，認為絕無可能思考與分析。但現代學者有人認為她不是低估機器(今天的電腦)的能力，而是太高估人腦的功能。

 

反對派之代表：「中文密室」

 

好事者：這豈不是「判定問題」2.0？是大智慧還是大膽怯？這麼不數學。

 

電腦之父，功績盤點

提出圖靈機 (他自己叫 a-Machine) 的概念，明確定義了「演算法」

（演算法就是圖靈機能做的事情）

 

0101

流程編碼、資料編碼（因為編碼，所以全能）

Store-Program （范諾伊曼 / 范紐曼受他影響而大力主張）

von Neumann 有名的手稿（沒附 reference、由助手打字，油印了 24 份，一時廣為流傳，戰後英美各機構競相打造

所有今天的電腦，就是圖靈機

 

 

才華洋溢、學識廣博

動物斑紋的形成

 

 

網路上的短影片 或長影片

在 YouTube 上觀看「Alan Turing - Celebrating the life of a genius」

在 YouTube 上觀看「The Inner Workings of an Enigma Machine 」

在 YouTube 上觀看「Alan Turing - betrayed by the country he saved」

在 YouTube 上觀看「Is The Imitation Game a historically accurate movie? 」

在 YouTube 上觀看「Turing: Pioneer of the Information Age 」

在 YouTube 上觀看「Dr. Andrew Hodges — Alan Turing: The Enigma 」

在 YouTube 上觀看「在 YouTube 上觀看「Prof: Alan Turing Decoded | Dermot Turing | Talks at Google 」

在 YouTube 上觀看「 Alan Turing Decoded: An Evening with Sir Dermot Turing 」

在 YouTube 上觀看「The enigma of WWII codebreaker Alan Turing 」

 

 

 

千古奇才、悲劇隕落

十五歲看懂相對論，做成筆記書教他媽媽

...

...

 

制度不平、考驗文明

 

 

性別不平等在人類社會仍然存在

有些細微、有些好懂

韓國產科禁止向準父母透漏超音波性別結果。話術：「嗯，小孩像媽媽噢」

女性軍人比例（打打殺殺，女人不行？）

宿舍為什麼要分男女？

廁所為什麼要男女？

 

窮究理哲(科學)、洗滌人性

 

 

因為稀有，所以珍貴

我們現在還沒有全部的答案

問對了問題，科學就會進步。

人類所喜愛的東西，不少是因為罕見而更高價值，如寶石與古董。

對於少數群體，我們除平權無歧視對待外，更應稀少

 

Extra

 

演講海報