喔對了，再補個書點。有一本翻譯的懸疑小說叫《圖靈的毒蘋果》(The Fall of Man in Wilmslow)，作者是接下續寫《龍紋身的女孩》系列的David Lagercrantz。這本小說也是跟Turing有關的題材但有多少內容是跟Turing的哲學有關我就不得而知了。我自己是沒看過這本小說啦，但是未來有機會我應該是會找來讀看看吧。
Turing這兩個概念在他1936年的論文——“On the Computable Numbers, with an Application to the Entscheidungsproblem”——中就以異常白話的方式給出其定義。當時的數學跟邏輯研究的背景，已經發現了羅素悖論跟眾多解決方案（包含the type theory、直覺主義、邏輯主義，跟Hilbert的有限形式主義）以及羅素跟Whitehead的形式化邏輯系統（包含一階邏輯跟把算術化約成邏輯的工作）、ZFC公理化集合論，以及Godel的兩個不完備性定理。
當時一個最基本的問題是：全稱算術語句——例如「對所有a、b和c來說，( a + b ) × c = ( a × c ) + ( b × c )」或著「不存在最大的質數」——有無限多例證的語句，但既然是無限多，我們要怎麼知道這樣的語句是真或是假？問題在於「所有」跟「不存在」（這相當於說「任何都不是」）都是這些語句的一部份；但事實上，判斷它們為真時，卻又不實際上需要談論到「所有」（也就是無限多的）個例。再加上羅素悖論擺明了談「所有的集合所形成的集合」是自我矛盾的之後，這種有關於自我指涉（self-referrential）的語句都似乎碰上類似的困難。
這裡的討論很有趣，Turing認為維根斯坦似乎不把數學的形式化（formalization of mathematics）中的不明顯或隱藏的錯誤、困難（e.g. liar sentences）看作一回事，要不然他就不會說「從沒這種事出錯過」，而只說，真的出錯是我們誤用數學以外的東西，而不是數學本身。相對地，維根斯坦則認為Turing沒有認真看待我們為何要把數學嚴格形式化的問題，因為如果矛盾真的在數學形式化的過程中存在，這就表示這是數學本身這套語言遊戲該有的特性，困惑於這種矛盾句，並不會妨礙數學形式化的過程。
1950年的這篇文章裡，Turing還先解釋了他1936年即提出的概念：「不連續狀態機器」（discrete state machine），也就是圖靈算機一開始的雛形。「這種機器藉由突然的跳動和敲擊從一個特並狀態移動到下一個狀態」（p.91）當然這種機器只是設想出來的，因為每一種運動都是連續的（否則會碰到像是Elea School的Zeno提出的飛矢不動的那樣類似的悖論），但是圖靈算機可以被設想成專門執行這種不連續狀態的通用機器，至於實際上是什麼材料、物體執行了或實現了這些不連續狀態，則不是Turing所關心的問題。
有看過《模仿遊戲》這部電影的人，應該可以輕易回想起Benedict Cumberbatch所飾演的Alan Turing一角，在劇中其精湛的數學能力，幫助盟軍在二戰期間破解納粹的密碼機Enigma，以及Turing因為他個人的性向之故，最後選擇自殺的慘劇。電影是根據這本書的作者Andrew Hodges較長篇的Turing傳記Alan Turing: The Enigma（中譯：《艾倫·圖靈傳》（上下兩冊）由時報出版）所改編。所以我想，把Hodges這本小書當成是Turing傳記的簡明版也不為過。
但畢竟我關心的還是Turing的哲學跟邏輯想法，所以此噗也會主要關注在相關方面上，像是邏輯可決定性、機器能否思考、數學基礎、可計算性等。
（有點複雜的）心得下收。
但有多少內容是跟Turing的哲學有關我就不得而知了。我自己是沒看過這本小說啦，但是未來有機會我應該是會找來讀看看吧。接下來就hardcore一點了...因為從標題<杜林算機與可決定性問題>可以看出，這章涉及的是Turing Machine（俗稱「圖靈算機」）以及邏輯可決定性（logical decidability）這兩個Turing哲學裡最重要的概念。隨後幾章也都是圍繞這兩個概念來論述的。
希爾伯特（David Hilbert）當時發表了著名的23個問題，其中第二個問題問的就是算術公理的一致性（consistency）。
但是Godel的第一不完備性公理宣稱，任何能表達初階算術的系統S中，都存在一個語句G，使得G既不能從S中被證明(proved)出來也不能從S中被否證(disproved)；而第二不完備性定理則宣稱這樣的一個系統S中，有一個說「S是一致的」語句，本身不可以在S中被證明或否證。
他的證明方式我以後會再開噗整理。但關鍵在於Godel使用了一種編碼模式（i.e. Godel's numbering）把初階算術系統裡的每一個語句都編成一串數字，從中他建構一條自我指涉的語句，而造成像說謊者悖論一樣的、具有自我指涉特性的困難。所以希爾伯特要求的算術系統一致性和完備性就破滅了。
Turing說我們可以設想一個只能處理有限條件的機器或算機（computer，或譯作「計算的人」）著有一條帶子。帶子上很像底片方格一樣，一格一格地被分開。然後每個方格裡的符號都可以被機器掃描，而在每個時刻裡，只有一個方格裡的符號可以說成是被機器直接意識到的（pp.31-2）。所以對Turing而言，機器在這裡是一個有意識的心靈，可以對方格內的符號進行掃描。而機器的行為則是完全被方格的排列以及方格內機器掃描到的符號所決定的。
1.不是擦掉一個符號就是印出一個符號；
2.向左或向右移動一格；最後
3.改變成一個新的方格的排列。
因而一台機器可以完全透過以上1~3這樣的「行為表」所定義，因此，每一個行為表都是一台圖靈算機。根據Hodges，「機器的行為形式受到很多限制，但杜林的論旨是，這些有限的行為形式構成一組基本元素，可以從它們組成所有的數學運算」（p.33）。
此外，為了讓機器能更接近人類真正的思考模式，Turing設想被掃描到的新方格跟之前已被掃描的方格之間距離不能過長——假設中間最多只能隔L個方格好了——藉此他更精確地定義何謂簡單運算：
1.在一個「被掃瞄方格」上符號的改變，與心靈狀態的一個可能改變。
2.與先前「被掃描方格」相距L方格之內，其中一個方格的變化，與心靈狀態的一個改變。
首先將所有圖靈算機按照行為表的字母排序給排列出來，先把那些不能印出無限小數的算機給排除，只留下那些可以印出可計算數目字的算機就好；接著使用二進位把數目字記為由0和1構成的數，然後定義一個新的數目字，讓它的第n個數字與第n個圖靈算機印出的數字不同，使得這個新的數目字至少在一個地方（e.g.第n個數字）與每個可計算數目字不同，因而完成證明——這個新構造的數目字是不可計算的。
這個弔詭的問題其背後的答案是：一開始去指認那些無法印出無限多數字的圖算機（並將之排除）的這個指認程序本身是不可被計算的，i.e.不存在一台圖靈算機可以檢查其他算機的行為表來決定他們是否能印出無限多的數字；「更直接說是：如果有這樣一個機器，它可以適用在自己身上，則這個觀念會導出矛盾」（p.43），而這就是所謂的「停機問題」（the halting problem）。
隔了好幾天沒把閱讀心得補上，原因有幾個：一是這幾天忙其他的事，都沒時間坐下來好好寫。自己也知道這樣是不好的習慣，但就把它當作是警惕吧！
二是糾結於譯者翻譯《杜林》這本書時，很多邏輯術語應該是翻得一團亂，特別是Turing自己的用詞跟其他邏輯學家用的詞不一樣；Turing談圖靈機都是用"computable"但是接下來要談的邏輯學家Alonzo Church證明了類似的定理，但是卻用"calculable"。在這方面，我想譯者應該把很多原文處出現的這兩個形容詞都混著翻成「可計算的」，所以雖然書早已閱畢多日，但還是花了些時間釐清哪個詞是誰用的詞。
好啦，抱怨完了，思考紀錄跟閱讀心得還是要繼續！
--------------------
而且2是由可定義性（definability）這個概念下手分析effective calculability的。由此，說一個函數f是effectively calculable，根據Church，就是在說f是一個可定義的函數；而可定義的函數可以完全透過Church用λ-calculas的方式建構出來。這就是所謂的Church Thesis。
Turing證明Church Thesis跟Turing Thesis是等價的，所以後來邏輯學家就合稱這個要旨為the Church-Turing Thesis，也就是任何函數是effectively calculable iff 它也是effectively computable。
維根斯坦認為這樣的思路可以持續下去，但是這又如何？對他來說，這不過是無用的語言遊戲罷了。
維根斯坦回應Turing說，或許在應用上造成傷害的確是該被防範的，可是在數學內為何人們需要害怕矛盾呢？
Turing回答說，因為我們無法在數學內對我們的計算非常有自信不會出錯，除非你已經知道這個理論內部隱藏著矛盾，否則，沒有人能百分百宣稱自己的計算無誤。
可是Turing反駁他說，即使理論沒有矛盾，你還是無法知道橋會不會斷，但如果我們知道矛盾存在，理論的應用一定會在某處出錯。維根斯坦則是聳聳肩答道「但從來沒有這種事出錯過」（p.67）
這種大膽的想法，根據Hodges，或許多少涉及了他的學術訓練、童年成長背景，以及當時蔚為風潮的心理行為主義的影響。
1. 神學上的反駁：思考是靈魂獨有的功能，機器跟動物不在神賜予思考的範圍之內，因此，不論是人以外的動物還是機器，都不可能思考。這乍看之下漏洞百出的反駁其實也不是沒有道理，有些東西還的確是人所獨有的，比如Hodges談到權威、責任，甚至道德等等。但Turing沒有很認真地對待這個反駁，對他而言，神賜予人類思考這個能力，純粹只是一個操作型的定義。而至於為什麼得這樣接受，還需要有其他更強的理由才行。
但是Hodges評論說，Searle的論證裡有兩個假設：一是有一個可以將中、英文互譯的算法；二是這個算法不是由機器執行，而是由房間裡的一個人所執行。
終於...寫完了QQ
這本應該是目前「閱讀哲學家系列」裡讀起來最難的一本。很多地方譯者感覺不是很用心，專有名詞的譯法也是很讓人混淆，所以閱讀過程中也得靠前後文去反覆推敲，再靠著一些自己知道的關於邏輯、心靈哲學的知識去補，才能夠把這篇寫完。