都聽過圖靈機,它的靈感來自哪兒?
作者:田達瑋 房天宇 秦曾昌
編輯:婉珺
人類,從來都不缺計算工具。
從中國的算籌、算盤,到西方帕斯卡、萊布尼茲等製造的計算器,這些古老的計算工具雖然能夠進行加減乘除、乘方以及開方運算,在當時大大地加快了人們的運算速度,但與我們今天所理解的計算機相去甚遠——這些古老的計算器,往往只能完成某一項特定任務;而今天,在計算機上只要點開不同的程序,就能完成各種不同的任務。
這種能解決各式各樣問題的計算機,都屬於圖靈機。
什麼是圖靈機?
圖靈機是圖靈在他24歲發表的論文(《論可計算數及其在判定問題中的應用》)中提出的一種抽象模型。這種當時只存在於想像中的機器由一個控制器、一個讀寫頭和一根無限長的工作帶組成的。紙帶起著存儲的作用;讀寫頭能夠讀取紙帶上的信息,以及將運算結果寫進紙帶;控制器則負責對搜集到的信息進行處理。
一個圖靈機的示意裝置。圖片來源:GabrielF|wikipedia
圖靈機的結構看起來非常簡單,但事實上,它與算盤之類的古老計算器有本質的區別:如果在控制器中輸入不同的程序,它就能夠處理不同的任務。這意味著,圖靈機實際上是一種「通用計算機」。
雖然圖靈機因圖靈而得名,但給予圖靈靈感的卻很可能是著名的「失敗」發明家查爾斯·巴貝奇。
「失敗」的發明家
巴貝奇
查爾斯巴貝奇(1791-1871)對數學和機械都有著極高天賦,他在18歲時以優異的成績考入劍橋大學。在大學期間,巴貝奇注意到了一個現象:當時歐洲的數學用表存在大量的錯誤。一項普查發現,在40本數表中,有3700個錯誤,而且大部分是由於手工計算和印刷造成的。這讓巴貝奇難以接受,他認為如果能用一台機器代替人工計算同時自動列印出數表,那麼這些問題就可以得到解決。而這台機器,就是著名的「差分機」。
圖片來源:wikimedia
當然,要製造這樣一台機器需要巨大的資金來源,巴貝奇開始向政府尋求幫助。在政府看來,當時數學用表的錯誤確實給航運以及建築業帶來了極大的不便,如果巴貝奇的「差分機」能夠成功,將會減少船隻觸礁以及房屋橋樑倒塌事故的發生,因此有意願資助他。
於是,在政府的支持下,巴貝奇完成了能夠進行4級拆分的差分機。這台差分機的運算速度之快和錯誤率之低已經遠遠領先於當時手工計算水平。
「差分機」的成功研製,讓巴貝奇備受鼓舞。他打算繼續研製精度更高、運算速度更快的「差分機2號」。也是在研製「差分機2號」的時候,巴貝奇開始構想另一種結構更簡單,功能更全面的機器——分析機。「分析機」有一種被稱為「孔卡」的結構,給「孔卡」編寫不同的程序,就可以讓分析機解決不同種類的問題。這一構想其實與圖靈機的「控制器」異曲同工。
巴貝奇的分析機(部分測試版)。1833年,一位不滿18歲的女孩被「分析機」的構想深深吸引(這個女孩便是歷史上第一位程序員愛達,Ada Augusta Byron)。1842年,愛達熱心地將一位義大利數學家發表的闡釋巴貝奇分析機原理和性能的文章翻譯成英文,並且在備註中,寫下了一段程序,這段程序,被認為是第一段計算機程序。圖片來源:Bruno Barral|Wikipedia
可惜的是,巴貝奇輸給了時代。巴貝奇的概念太過超前,以至於當時的人們無法驗證他的猜想,也無法建造出他理想中的機器(直到二十世紀末,人們才按照巴貝奇的設計造出了「差分機2號」)。
巴貝奇至死都沒有見到「差分機2號」和「分析機」問世。而當時英國政府向巴貝奇資助的1.7萬英鎊,最終也打了水漂。這讓不少人認為巴貝奇是個失敗者,他的「分析機」構想也沒有再引起人們的關注。
圖靈機的誕生
直到近一個世紀後,大名鼎鼎的圖靈提出了一種能模擬人類進行數學計算過程的機器,圖靈稱之為A-machine,也就是我們所熟知的圖靈機。A-machine很大程度上模仿了人類處理問題的過程:它擁有一個類似於人眼和手的讀寫頭能夠讀取信息以及輸出信息;一條無限長的紙帶,源源不斷地提供信息以及供輸出結果; 一個類似於我們大腦的控制器,能夠根據問題不同,進行不同的處理。
理論上來說,任何能夠用數學解決的問題都能交由圖靈機來處理,這一構想與巴貝奇所追求的「完全由機器來分析和處理問題」十分一致。圖靈的學生以及合作者羅賓·甘迪,也發現了巴貝奇分析機的理論中有不少與圖靈機理論異曲同工之處,因此推測分析機是圖靈機的靈感來源。
阿蘭·圖靈。圖片來源:turingarchive.org
相較於巴貝奇,圖靈是幸運的。他的理論在接下來的十幾年時間裡便得到了驗證,並逐漸發展成為我們今天的計算機。
自圖靈機模型提出以來,至今已經歷了八十年時間。人們對圖靈機模型進行拓展,誕生了一批改進版的圖靈機,如雙向無限帶圖靈機、多頭圖靈機、非確定型圖靈機、多維圖靈機等。但這些模型,僅是對運算速度等進行了提升,並沒有提出超越圖靈機的新模型。超越圖靈機的偉大構想,說不定已經在醞釀中。
可以肯定的是,超越圖靈機的全新計算機,必將給人工智慧技術帶來一次巨大的飛躍。
作者名片
編輯:婉珺
排版:曉嵐
題圖來源:wikipedia
歡迎個人轉發到朋友圈
本文來自果殼網
掃碼立刻漲知識!
從論文到科普,只有一步
GIF
趕緊跑來點贊
![](https://pic.pimg.tw/zzuyanan/1488615166-1259157397.png)
![](https://pic.pimg.tw/zzuyanan/1482887990-2595557020.jpg)
TAG:果殼科學人 |