帶你深入理解圖靈機——天才所在的時代
2018-8-8 09:34
來源：
Uni-times
這幾年由于區塊鏈的大熱，以太坊獨特的solidity語言實現智能合約功能，圖靈完備這個詞走進大家的視線。
沒有計算機專業知識的同學其實很難理解這個詞的意思，其實計算機專業的同學都沒有深入理解圖靈機，圖靈完備，圖靈測試等概念包含的內涵。
為了方便理解區塊鏈技術，理解智能合約，筆者準備分幾篇文章來帶大家從淺入深，一步一步帶你深入理解圖靈機，相信通過這幾篇文章能就能夠理解什么是圖靈完備。
大家知道任何偉大藝術的誕生背后都有迷人的時代背景，偉大的科學思想也是一樣。從達芬奇到蒙拉麗莎的微笑；從牛頓到萬有引力；從愛因斯坦到相對論；偉大的天才圖靈和這些大師一樣有同樣讓人著迷的時代和故事。
艾倫·麥席森·圖靈（Alan Mathison Turing，1912年6月23日－1954年6月7日），英國數學家、邏輯學家，被稱為計算機科學理論之父，人工智能之父。
1931年，圖靈考入劍橋大學國王學院，由于成績優異而獲得數學獎學金。
1936年5月，年僅24歲的圖靈發表一篇題為《論數字計算在決斷難題中的應用》的論文，論文中提出一種計算裝置，后被稱為“圖靈機”，圖靈機不是具體的計算機，而是一種計算概念、計算理論。
1938年在普林斯頓獲博士學位，其論文題目為“以序數為基礎的邏輯系統”，在數理邏輯研究中產生了深遠的影響；同年圖靈回到英國，在劍橋大學國王學院任研究員。
第二次世界大戰期間，1939年圖靈到英國外交部通信處從事軍事工作，主要是破譯敵方密碼的工作。由于破譯工作的需要，他參與了世界上最早的電子計算機的研制工作。他的工作取得了極好的成就，破譯了德國人Enigma密碼，于1945年獲政府的最高獎——大英帝國榮譽勛章。
945年，圖靈結束了在外交部的工作，他試圖恢復戰前在理論計算機科學方面的研究，具體研制出新的計算機來。
1950年他發表論文《計算機器與智能》（ Computing Machinery and Intelligence），為后來的人工智能科學提供了開創性的構思。提出著名的圖靈測試。
1950年，1950年10月，圖靈發表論文《機器能思考嗎》。這一劃時代的作品，使圖靈贏得了“人工智能之父”的桂冠。此時，人工智能也進入了實踐研制階段。隨著這幾年AI技術的不斷成熟，人們越來越認識到圖靈思想的深刻性：它們至今仍然是人工智能的主要思想之一。
1954年6月7日，年僅41歲的圖靈被發現死于家中的床上，床頭還放著一個被咬了一口的蘋果。這就是現在大名鼎鼎的蘋果電腦公司logo的來源。
從圖靈的生平中，我們知道，他出生在20世紀初，1912年。
在世界國家格局上，這個時候剛剛爆發第一次世界大戰（1913~1921），緊接著1939年至1945年第二次世界大戰，大家知道，這兩次世界大戰倒逼了很多科技的發展，二戰期間恰好是圖靈青年時代。
在科技文明發展上，由于邏輯的數學化，促使了數理邏輯學科的誕生和發展。但同時這個時期數學上發生了第三次數學危機，具體介紹在下方。圖靈在劍橋讀大學期間，修讀了“數學基礎”課程，授課人是紐曼，紐曼整個課程包含對哥德爾不完備性定理的證明和尚未解決的判定性問題。
這些科技事件的背后，其實是人們在認知上，對可計算性理論的研究，圖靈正是這個問題終結者。
順便提一下，愛因斯坦1905年提出狹義相對論，1927年年僅15歲的圖靈為了幫助母親理解相對論，還寫過論文的摘要。
在20世紀以前，人們普遍認為，所有的問題類都是有算法的，人們的計算研究就是找出算法來。1900年，當時著名的大數學家希爾伯特在世紀之交的數學家大會上給國際數學界提出了著名的23個數學問題。
其中第十個問題是這樣的：
存在不存在一種有限的、機械的步驟能夠判斷“丟番圖方程”是否存在解？
“丟番圖方程”指：有一個或者幾個變量的整系數方程，它們的求解僅僅在整數范圍內進行。
上面這個問題簡單點解釋是：隨便給一個不確定的方程，是否通過有限的步驟運算，判斷這個方程是否存在整數解。
這個問題在1970年，蘇聯一個數學家證明了其實很多數學問題，是沒有答案，甚至沒有答案的問題比有答案的問題還要多。
這里就提出來了有限的、機械的證明步驟的問題，其實就是算法。但在當時，人們還不知道“算法”是什么。實際上，當時數學領域中已經有很多問題都是跟“算法”密切相關的，因而，科學的 “算法” 定義呼之欲出。之后到了30年代的時候，終于有兩個人分別提出了精確定義算法的方法，一個人是圖靈，一個人是丘奇。而其中圖靈提出來的圖靈機模型直觀形象。
圖靈思考這個問題的方式和常人不一樣，在寫前面提到的論文《論可計算數及其在判定性問題上的應用》的時候，圖靈在思考三個問題：
世界上是否所有的數學問題都有明確的答案？
如果有明確的答案，是否可以通過有限步驟的計算得到答案？
對于那些有可能在有限步驟計算出來的學習問題，是否有一種假想的機械，讓它不斷運行，最后機器停下來的時候，那個數學答案就計算出來了？
圖靈這樣的天才考慮問題的認知是高屋建瓴的。
圖靈首先考慮的是是否所有數學問題都用解，如果這個問題不解決，辛辛苦苦解題，最后發現無解，一切的努力都是浪費時間和精力。
對于存在答案的數學問題，只有部分是可以在有限步驟內完成，這樣把計算機的邊界確定下來了。
確定了邊界之后，就要設計一種通用、有效、等價的機器，保證可以按照這個方法做事，最后得到答案。而圖靈機就是圖靈設計出來的這樣的一個機器，嚴格來講是一種數學模型、計算理論模型。
從圖靈機提出到現在已經過去了80多年，今天所有的計算機，包括量子計算機都沒有超出圖靈機的理論范疇。
第三次數學危機產生于十九世紀末和二十世紀初，當時正是數學空前興旺發達的時期。首先是邏輯的數學化，促使了數理邏輯這門學科誕生。
早在19世紀末的時候，康托爾為集合論做了奠基性的研究。人們發現，運用集合這個概念可以概括所有的數學，也就是說集合是一切數學的基礎。然而就當這座大廈即將完工的時候，一件可怕的事情發生了，羅素提出來的羅素悖論粉碎了數學家的夢想。
關于羅素悖論的一個通俗化版本是：
“村子里有一個理發師，他給自己定了一條規矩：‘不給那些所有給自己理發的人理發’。
現在就要問，這個理發師該不該給自己理發？”。
如果你嘗試回答這個問題就會發現奇怪的事情：這個問題本身似乎是不可能的！
為什么要第三次數學危機呢？
因為有個很重要的概念：停機問題，停機問題是邏輯數學中可計算性理論中很重要的問題，也是第三次數學危機的解決方案。
停機問題通俗地說，停機問題就是判斷任意一個程序是否能在有限的時間之內結束運行的問題。該問題等價于如下的判定問題：是否存在一個程序P，對于任意輸入的程序w，能夠判斷w會在有限時間內結束或者死循環。
有人猜測圖靈機模型是圖靈在思考停機問題而順帶設計出來的，是很有道理的。
圖靈在劍橋大學國王學院期間，研究過一本叫做《量子力學的數學基礎》的新書，這本書由年輕的匈牙利數學家約翰·馮·諾依曼所著。圖靈意識到計算可以用確定性的機械運動來進行表示。其實我們現在的電子計算機雖然不是我們傳統意義上的機械，但是CPU內部的電子運動等價于機械運動。
同時圖靈也意識到人的思想、意識來自于量子力學中的測不準原理，這不光是微觀世界，同時也是這個宇宙本身的規律。所以圖靈意識到計算是確定性的，可判定的，而意識是不定的，不可計算的。
在AI人工智能有巨大發展的今天，很多人擔心計算機是否會和人一樣有意識，其實圖靈在80多年前已經考慮過這個問題了。
前面提到，圖靈在1950年寫過一篇論文《計算機器與智能》，在這篇論文中，圖靈測試一詞被提出來：
指測試者與被測試者（一個人和一臺機器）隔開的情況下，通過一些裝置（如鍵盤）向被測試者隨意提問。進行多次測試后，如果有超過30%的測試者不能確定出被測試者是人還是機器，那么這臺機器就通過了測試，并被認為具有人類智能。
這個測試有多難？目前我們所有的人工智能都沒有完成這個測試。最近2018年3月份的谷歌I/O大會上演示的AI產品，據說“部分通過圖靈測試”。這個部分到底有多少也未可知。
從人類科技發展的歷史上來看，19世紀末到20世紀中期，是第二次工業革命和第三工業革命過渡的時期。
第二次工業革命主要電和磁、內燃機的發明和使用，發展到這個時候科學家對世界的認知越來越多，越來越清晰，物理學和數學等自然科學發展迅速。
這個時候的數學家發現很多現象可以用數學模型來表示，從物體的運動到星球的運動、從熱能到動能的轉換、從電到磁的轉換等等。那問題來了是否所有的現象都可以用數學模型來表達呢？真是這個問題，讓人們對數學很多根本性問題進行思考和研究。
中國有句古話說：亂世出英雄。在圖靈的時代，在科學歷史上出了很多的科學英雄，包括愛因斯坦、馮諾依曼、圖靈、哥德爾等等，一方面是時代背景使然，一方面真是他們的天賦和努力讓以信息化為代表的第三次工業革命的進程大大加快了。
從這些巨匠的思考問題，解決問題的方法和認知來看是超出常人的。從對可計算性理論的思考，給了我們很大的啟示：
作者：jerry邱
來源：簡書
版權申明：本內容來自于互聯網，屬第三方匯集推薦平臺。本文的版權歸原作者所有，文章言論不代表鏈門戶的觀點，鏈門戶不承擔任何法律責任。如有侵權請聯系QQ：3341927519進行反饋。
