姓名：張志遠(yuǎn) 學(xué)號(hào)：17021211150

轉(zhuǎn)載自：http://www.reibang.com/p/3817b9d5ff76

【嵌牛導(dǎo)讀】：圖靈機(jī)與人工智能之間有著深深的關(guān)系袍啡，作為人工智能之父踩官，圖靈提出的一些思想指的思考。

【嵌牛鼻子】：圖靈機(jī)

【嵌牛提問(wèn)】：機(jī)器能不能思考境输？

【嵌牛正文】：

這幾年由于區(qū)塊鏈的大熱，以太坊獨(dú)特的solidity語(yǔ)言實(shí)現(xiàn)智能合約功能颖系，圖靈完備這個(gè)詞走進(jìn)大家的視線嗅剖。

沒(méi)有計(jì)算機(jī)專業(yè)知識(shí)的同學(xué)其實(shí)很難理解這個(gè)詞的意思豁生，其實(shí)計(jì)算機(jī)專業(yè)的同學(xué)都沒(méi)有深入理解圖靈機(jī)衬鱼，圖靈完備，圖靈測(cè)試等概念包含的內(nèi)涵男旗。為了方便理解區(qū)塊鏈技術(shù)趁啸，理解智能合約强缘，筆者準(zhǔn)備分幾篇文章來(lái)帶大家從淺入深，一步一步帶你深入理解圖靈機(jī)不傅，相信通過(guò)這幾篇文章能就能夠理解什么是圖靈完備旅掂。

大家知道任何偉大藝術(shù)的誕生背后都有迷人的時(shí)代背景，偉大的科學(xué)思想也是一樣访娶。從達(dá)芬奇到蒙拉麗莎的微笑商虐；從牛頓到萬(wàn)有引力；從愛(ài)因斯坦到相對(duì)論崖疤；偉大的天才圖靈和這些大師一樣有同樣讓人著迷的時(shí)代和故事秘车。

圖靈的生平

艾倫·麥席森·圖靈（Alan Mathison Turing，1912年6月23日－1954年6月7日）劫哼，英國(guó)數(shù)學(xué)家叮趴、邏輯學(xué)家，被稱為計(jì)算機(jī)科學(xué)理論之父权烧，人工智能之父眯亦。

1931年伤溉，圖靈考入劍橋大學(xué)國(guó)王學(xué)院，由于成績(jī)優(yōu)異而獲得數(shù)學(xué)獎(jiǎng)學(xué)金搔驼。

1936年5月谈火，年僅24歲的圖靈發(fā)表一篇題為《論數(shù)字計(jì)算在決斷難題中的應(yīng)用》的論文，論文中提出一種計(jì)算裝置舌涨，后被稱為“圖靈機(jī)”糯耍，圖靈機(jī)不是具體的計(jì)算機(jī)，而是一種計(jì)算概念囊嘉、計(jì)算理論温技。

1938年在普林斯頓獲博士學(xué)位，其論文題目為“以序數(shù)為基礎(chǔ)的邏輯系統(tǒng)”扭粱，在數(shù)理邏輯研究中產(chǎn)生了深遠(yuǎn)的影響舵鳞；同年圖靈回到英國(guó)，在劍橋大學(xué)國(guó)王學(xué)院任研究員琢蛤。

第二次世界大戰(zhàn)期間蜓堕，1939年圖靈到英國(guó)外交部通信處從事軍事工作，主要是破譯敵方密碼的工作博其。由于破譯工作的需要套才，他參與了世界上最早的電子計(jì)算機(jī)的研制工作。他的工作取得了極好的成就慕淡，破譯了德國(guó)人Enigma密碼背伴，于1945年獲政府的最高獎(jiǎng)——大英帝國(guó)榮譽(yù)勛章。

圖靈破解密碼

1945年峰髓，圖靈結(jié)束了在外交部的工作傻寂，他試圖恢復(fù)戰(zhàn)前在理論計(jì)算機(jī)科學(xué)方面的研究，具體研制出新的計(jì)算機(jī)來(lái)携兵。

1950年他發(fā)表論文《計(jì)算機(jī)器與智能》（ Computing Machinery and Intelligence）疾掰，為后來(lái)的人工智能科學(xué)提供了開(kāi)創(chuàng)性的構(gòu)思。提出著名的圖靈測(cè)試眉孩。

1950年个绍，1950年10月，圖靈發(fā)表論文《機(jī)器能思考嗎》浪汪。這一劃時(shí)代的作品巴柿，使圖靈贏得了“人工智能之父”的桂冠。此時(shí)死遭，人工智能也進(jìn)入了實(shí)踐研制階段广恢。隨著這幾年AI技術(shù)的不斷成熟，人們?cè)絹?lái)越認(rèn)識(shí)到圖靈思想的深刻性：它們至今仍然是人工智能的主要思想之一呀潭。

1954年6月7日钉迷，年僅41歲的圖靈被發(fā)現(xiàn)死于家中的床上至非，床頭還放著一個(gè)被咬了一口的蘋(píng)果。這就是現(xiàn)在大名鼎鼎的蘋(píng)果電腦公司logo的來(lái)源糠聪。

時(shí)代背景

從圖靈的生平中荒椭，我們知道，他出生在20世紀(jì)初舰蟆，1912年趣惠。

在世界國(guó)家格局上，這個(gè)時(shí)候剛剛爆發(fā)第一次世界大戰(zhàn)（1913~1921）身害，緊接著1939年至1945年第二次世界大戰(zhàn)味悄，大家知道，這兩次世界大戰(zhàn)倒逼了很多科技的發(fā)展塌鸯，二戰(zhàn)期間恰好是圖靈青年時(shí)代侍瑟。

在科技文明發(fā)展上，由于邏輯的數(shù)學(xué)化丙猬，促使了數(shù)理邏輯學(xué)科的誕生和發(fā)展涨颜。但同時(shí)這個(gè)時(shí)期數(shù)學(xué)上發(fā)生了第三次數(shù)學(xué)危機(jī)，具體介紹在下方茧球。圖靈在劍橋讀大學(xué)期間咐低，修讀了“數(shù)學(xué)基礎(chǔ)”課程，授課人是紐曼袜腥，紐曼整個(gè)課程包含對(duì)哥德?tīng)柌煌陚湫远ɡ淼淖C明和尚未解決的判定性問(wèn)題。

這些科技事件的背后钉汗，其實(shí)是人們?cè)谡J(rèn)知上羹令，對(duì)可計(jì)算性理論的研究，圖靈正是這個(gè)問(wèn)題終結(jié)者损痰。

隨便提一下福侈，愛(ài)因斯坦1905年提出狹義相對(duì)論，1927年年僅15歲的圖靈為了幫助母親理解相對(duì)論卢未，還寫(xiě)過(guò)論文的摘要肪凛。

可計(jì)算性理論

在20世紀(jì)以前，人們普遍認(rèn)為辽社，所有的問(wèn)題類都是有算法的伟墙，人們的計(jì)算研究就是找出算法來(lái)。1900年滴铅，當(dāng)時(shí)著名的大數(shù)學(xué)家希爾伯特在世紀(jì)之交的數(shù)學(xué)家大會(huì)上給國(guó)際數(shù)學(xué)界提出了著名的23個(gè)數(shù)學(xué)問(wèn)題戳葵。

其中第十問(wèn)題是這樣的：

存在不存在一種有限的、機(jī)械的步驟能夠判斷“丟番圖方程”是否存在解汉匙？

“丟番圖方程”指：有一個(gè)或者幾個(gè)變量的整系數(shù)方程拱烁，它們的求解僅僅在整數(shù)范圍內(nèi)進(jìn)行生蚁。

上面這個(gè)問(wèn)題簡(jiǎn)單點(diǎn)解釋是：隨便給一個(gè)不確定的方程，是否通過(guò)有限的步驟運(yùn)算戏自，判斷這個(gè)方程是否存在整數(shù)解邦投。

這個(gè)問(wèn)題在1970年，蘇聯(lián)一個(gè)數(shù)學(xué)家證明了其實(shí)很多數(shù)學(xué)問(wèn)題擅笔，是沒(méi)有答案志衣，甚至沒(méi)有答案的問(wèn)題比有答案的問(wèn)題還要多。

這里就提出來(lái)了有限的剂娄、機(jī)械的證明步驟的問(wèn)題蠢涝，其實(shí)就是算法。但在當(dāng)時(shí)阅懦，人們還不知道“算法”是什么和二。實(shí)際上，當(dāng)時(shí)數(shù)學(xué)領(lǐng)域中已經(jīng)有很多問(wèn)題都是跟“算法”密切相關(guān)的耳胎，因而惯吕，科學(xué)的 “算法” 定義呼之欲出。之后到了30年代的時(shí)候怕午，終于有兩個(gè)人分別提出了精確定義算法的方法废登，一個(gè)人是圖靈，一個(gè)人是丘奇郁惜。而其中圖靈提出來(lái)的圖靈機(jī)模型直觀形象堡距。

圖靈思考這個(gè)問(wèn)題的方式和常人不一樣，在寫(xiě)前面提到的論文《論可計(jì)算數(shù)及其在判定性問(wèn)題上的應(yīng)用》的時(shí)候兆蕉，圖靈在思考三個(gè)問(wèn)題

世界上是否所有的數(shù)學(xué)問(wèn)題都有明確的答案羽戒？

如果有明確的答案，是否可以通過(guò)有限步驟的計(jì)算得到答案虎韵？

對(duì)于那些有可能在有限步驟計(jì)算出來(lái)的學(xué)習(xí)問(wèn)題易稠，是否有一種假想的機(jī)械，讓它不斷運(yùn)行包蓝，最后機(jī)器停下來(lái)的時(shí)候驶社，那個(gè)數(shù)學(xué)答案就計(jì)算出來(lái)了？

圖靈這樣的天才考慮問(wèn)題的認(rèn)知是高屋建瓴的测萎。

圖靈首先考慮的是是否所有數(shù)學(xué)問(wèn)題都用解亡电，如果這個(gè)問(wèn)題不解決，辛辛苦苦解題绳泉，最后發(fā)現(xiàn)無(wú)解逊抡，一切的努力都是浪費(fèi)時(shí)間和精力。

對(duì)于存在答案的數(shù)學(xué)問(wèn)題，只有部分是可以在有限步驟內(nèi)完成冒嫡，這樣把計(jì)算機(jī)的邊界確定下來(lái)了拇勃。

確定了邊界之后，就要設(shè)計(jì)一種通用孝凌、有效方咆、等價(jià)的機(jī)器，保證可以按照這個(gè)方法做事蟀架，最后得到答案瓣赂。而圖靈機(jī)就是圖靈設(shè)計(jì)出來(lái)的這樣的一個(gè)機(jī)器，嚴(yán)格來(lái)講是一種數(shù)學(xué)模型片拍、計(jì)算理論模型煌集。

從圖靈機(jī)提出到現(xiàn)在已經(jīng)過(guò)去了80多年，今天所有的計(jì)算機(jī)捌省，包括量子計(jì)算機(jī)都沒(méi)有超出圖靈機(jī)的理論范疇苫纤。

第三次數(shù)學(xué)危機(jī)與停機(jī)問(wèn)題

第三次數(shù)學(xué)危機(jī)產(chǎn)生于十九世紀(jì)末和二十世紀(jì)初，當(dāng)時(shí)正是數(shù)學(xué)空前興旺發(fā)達(dá)的時(shí)期纲缓。首先是邏輯的數(shù)學(xué)化卷拘，促使了數(shù)理邏輯這門(mén)學(xué)科誕生。

早在19世紀(jì)末的時(shí)候祝高，康托爾為集合論做了奠基性的研究栗弟。人們發(fā)現(xiàn)，運(yùn)用集合這個(gè)概念可以概括所有的數(shù)學(xué)工闺，也就是說(shuō)集合是一切數(shù)學(xué)的基礎(chǔ)乍赫。然而就當(dāng)這座大廈即將完工的時(shí)候，一件可怕的事情發(fā)生了陆蟆，羅素提出來(lái)的羅素悖論粉碎了數(shù)學(xué)家的夢(mèng)想耿焊。

關(guān)于羅素悖論的一個(gè)通俗化版本是：

“村子里有一個(gè)理發(fā)師，他給自己定了一條規(guī)矩：‘不給那些所有給自己理發(fā)的人理發(fā)’遍搞。

現(xiàn)在就要問(wèn)，這個(gè)理發(fā)師該不該給自己理發(fā)器腋？”溪猿。

如果你嘗試回答這個(gè)問(wèn)題就會(huì)發(fā)現(xiàn)奇怪的事情：這個(gè)問(wèn)題本身似乎是不可能的！

為什么要第三次數(shù)學(xué)危機(jī)呢纫塌？

因?yàn)橛袀€(gè)很重要的概念：停機(jī)問(wèn)題诊县，停機(jī)問(wèn)題是邏輯數(shù)學(xué)中可計(jì)算性理論中很重要的問(wèn)題，也是第三次數(shù)學(xué)危機(jī)的解決方案措左。

停機(jī)問(wèn)題通俗地說(shuō)依痊，停機(jī)問(wèn)題就是判斷任意一個(gè)程序是否能在有限的時(shí)間之內(nèi)結(jié)束運(yùn)行的問(wèn)題。該問(wèn)題等價(jià)于如下的判定問(wèn)題：是否存在一個(gè)程序P，對(duì)于任意輸入的程序w胸嘁，能夠判斷w會(huì)在有限時(shí)間內(nèi)結(jié)束或者死循環(huán)瓶摆。

有人猜測(cè)圖靈機(jī)模型是圖靈在思考停機(jī)問(wèn)題而順帶設(shè)計(jì)出來(lái)的，是很有道理的性宏。

人工智能

圖靈在劍橋大學(xué)國(guó)王學(xué)院期間群井，研究過(guò)一本叫做《量子力學(xué)的數(shù)學(xué)基礎(chǔ)》的新書(shū)，這本書(shū)由年輕的匈牙利數(shù)學(xué)家約翰·馮·諾依曼所著毫胜。圖靈意識(shí)到計(jì)算可以用確定性的機(jī)械運(yùn)動(dòng)來(lái)進(jìn)行表示书斜。其實(shí)我們現(xiàn)在的電子計(jì)算機(jī)雖然不是我們傳統(tǒng)意義上的機(jī)械，但是CPU內(nèi)部的電子運(yùn)動(dòng)等價(jià)于機(jī)械運(yùn)動(dòng)酵使。

同時(shí)圖靈也意識(shí)到人的思想荐吉、意識(shí)來(lái)自于量子力學(xué)中的測(cè)不準(zhǔn)原理，這不光是微觀世界口渔，同時(shí)也是這個(gè)宇宙本身的規(guī)律样屠。所以圖靈意識(shí)到計(jì)算是確定性的，可判定的搓劫，而意識(shí)是不定的瞧哟，不可計(jì)算的。

在AI人工智能有巨大發(fā)展的今天枪向，很多人擔(dān)心計(jì)算機(jī)是否會(huì)和人一樣有意識(shí)勤揩，其實(shí)圖靈在80多年前已經(jīng)考慮過(guò)這個(gè)問(wèn)題了。

前面提到秘蛔，圖靈在1950年寫(xiě)過(guò)一篇論文《計(jì)算機(jī)器與智能》陨亡，在這篇論文中，圖靈測(cè)試一詞被提出來(lái)：

指測(cè)試者與被測(cè)試者（一個(gè)人和一臺(tái)機(jī)器）隔開(kāi)的情況下深员，通過(guò)一些裝置（如鍵盤(pán)）向被測(cè)試者隨意提問(wèn)负蠕。進(jìn)行多次測(cè)試后，如果有超過(guò)30%的測(cè)試者不能確定出被測(cè)試者是人還是機(jī)器倦畅，那么這臺(tái)機(jī)器就通過(guò)了測(cè)試遮糖，并被認(rèn)為具有人類智能

這個(gè)測(cè)試有多難？目前我們所有的人工智能都沒(méi)有完成這個(gè)測(cè)試叠赐。最近2018年3月份的谷歌I/O大會(huì)上演示的AI產(chǎn)品欲账，據(jù)說(shuō)“部分通過(guò)圖靈測(cè)試”。這個(gè)部分到底有多少也未可知芭概。

總結(jié)與啟示

從人類科技發(fā)展的歷史上來(lái)看赛不，19世紀(jì)末到20世紀(jì)中期，是第二次工業(yè)革命和第三工業(yè)革命過(guò)渡的時(shí)期罢洲。第二次工業(yè)革命主要電和磁踢故、內(nèi)燃機(jī)的發(fā)明和使用，發(fā)展到這個(gè)時(shí)候科學(xué)家對(duì)世界的認(rèn)知越來(lái)越多，越來(lái)越清晰殿较，物理學(xué)和數(shù)學(xué)等自然科學(xué)發(fā)展迅速耸峭。這個(gè)時(shí)候的數(shù)學(xué)家發(fā)現(xiàn)很多現(xiàn)象可以用數(shù)學(xué)模型來(lái)表示，從物體的運(yùn)動(dòng)到星球的運(yùn)動(dòng)斜脂、從熱能到動(dòng)能的轉(zhuǎn)換抓艳、從電到磁的轉(zhuǎn)換等等。那問(wèn)題來(lái)了是否所有的現(xiàn)象都可以用數(shù)學(xué)模型來(lái)表達(dá)呢帚戳？真是這個(gè)問(wèn)題玷或，讓人們對(duì)數(shù)學(xué)很多根本性問(wèn)題進(jìn)行思考和研究。

中國(guó)有句古話說(shuō)：亂世出英雄片任。在圖靈的時(shí)代偏友，在科學(xué)歷史上出了很多的科學(xué)英雄，包括愛(ài)因斯坦对供、馮諾依曼位他、圖靈、哥德?tīng)柕鹊炔。环矫媸菚r(shí)代背景使然鹅髓，一方面真是他們的天賦和努力讓以信息化為代表的第三次工業(yè)革命的進(jìn)程大大加快了。

從這些巨匠的思考問(wèn)題京景，解決問(wèn)題的方法和認(rèn)知來(lái)看是超出常人的窿冯。從對(duì)可計(jì)算性理論的思考，給了我們很大的啟示：

要學(xué)會(huì)抽象确徙，看問(wèn)題高屋建瓴醒串，學(xué)會(huì)從上帝視角看問(wèn)題

知道做事情的邊界是非常重要的，可以指導(dǎo)人們?cè)谡_的范圍內(nèi)做事情鄙皇，可以減少很多無(wú)謂的付出芜赌。

做事情要有方法論，理解計(jì)算的等價(jià)性

要學(xué)好數(shù)學(xué)