科普 | 除了圖靈完備概念，還有圖靈測試、圖靈等價、圖靈機、圖靈獎_區塊鏈

關于圖靈完備，很多區塊鏈項目的白皮書中都說到自己的項目支持什么圖靈完備，或者圖靈等價，包括以前也說過以太坊的智能合約是圖靈完備的，比特幣舍棄了圖靈完備等等。了解圖靈完備有利于更好的理解區塊鏈領域中的技術。

從圖靈完備，我們可以整體的了解一下，圖靈、圖靈完備與圖靈等價、圖靈測試、圖靈機、圖靈獎。

1.圖靈本人

艾倫·麥席森·圖靈艾倫·麥席森·圖靈，1912年生于英國倫敦。艾倫·麥席森·圖靈少年時就表現出獨特的直覺創造能力和對數學的愛好。

1926年，他考入倫敦有名的舍本(Sherborne)公學，受到良好的中等教育。他在中學期間表現出對自然科學的極大興趣和敏銳的數學頭腦。

1931年，圖靈考入劍橋大學國王學院，由于成績優異而獲得數學獎學金。在劍橋，他的數學能力得到充分的發展。

1935年，當選為國王學院的研究員，并于次年榮獲英國著名的史密斯(Smith)數學獎，成為國王學院聲名顯赫的畢業生之一。

1936年5月，提出了“圖靈機”，它第一次在純數學的符號邏輯，和實體世界之間建立了聯系，為此后的計算機和“人工智能”奠定了理論基礎。

1936年9月，圖靈應邀到美國普林斯頓高級研究院學習，并與丘奇一同工作。

1938年夏，圖靈回到英國，仍在劍橋大學國王學院任研究員，繼續研究數理邏輯和計算理論，同時開始了計算機的研制工作。

動態 | 報告：區塊鏈等熱點詞促使童書科普百科類成交額同比增速最高:近日，京東圖書與艾瑞咨詢聯合發布了《2019中國圖書市場報告》。報告指出，AI、5G、區塊鏈、機器人、VR、智能家居、AR這些熱點詞，不斷點燃科技熱潮，科技在改變大眾生活的同時，也吸引了越來越多家長的關注，從小培養孩子對科技的興趣和熱愛。因此童書中科普百科類成交額同比增速最高，占比將近40%。[2020/1/8]

1939年秋，他應召到英國外交部通信處從事軍事工作，主要是破譯敵方密碼的工作。由于破譯工作的需要，他參與了世界上最早的電子計算機的研制工作。他的工作取得了極好的成就，因而于1945年獲政府的最高獎——大英帝國榮譽勛章(O．B．E．勛章)。

1945年，圖靈結束了在外交部的工作，他試圖恢復戰前在理論計算機科學方面的研究，并結合戰時的工作，具體研制出新的計算機來。這一想法得到當局的支持。同年，圖靈被錄用為泰丁頓(Teddington)國家物理研究所的研究人員，開始從事“自動計算機”(ACE)的邏輯設計和具體研制工作。

1945年到1948年，他在英國國家物理實驗室工作，負責自動計算引擎的研究。

1948年，圖靈接受了曼徹斯特大學的高級講師職務。

1949年成為曼徹斯特大學計算機實驗室的副主任，負責最早的真正意義上的計算機——“曼徹斯特一號”的軟件理論開發，因此成為世界上第一位把計算機實際用于數學研究的科學家。

1950年，并提出了著名的“圖靈測試”。

1950年，他提出關于機器思維的問題，他的論文“計算機和智能(Computingmachineryandintelligence)，引起了廣泛的注意和深遠的影響。1950年10月，圖靈發表論文《機器能思考嗎》。這一劃時代的作品，使圖靈贏得了“人工智能之父”的桂冠。

動態 | 人民日報官方微博科普區塊鏈 強調區塊鏈不等于比特幣:人民日報官方微博今早發表9圖科普區塊鏈。其中涉及區塊鏈的特點有：1、安全；2、不可篡改；3、可訪問；4、無第三方。區塊鏈對未來的影響：1、不需繁瑣個人證明；2、看病避免反復檢查；3、旅行消費更加便捷；4、交易無需第三方。同時強調，區塊鏈不等于比特幣。比特幣只是區塊鏈技術的一種應用，區塊鏈還有醫療衛生、食品安全、版權保護等諸多應用領域。[2019/10/28]

1951年，由于在可計算數方面所取得的成就，成為英國皇家學會會員，時年39歲。

1954年6月7日，圖靈被發現死于家中的床上，床頭還放著一個被咬了一口的蘋果，當時圖靈41歲。

2.圖靈完備與圖靈等價

圖靈完備：一切可計算的問題都能計算，這樣的虛擬機或者編程語言就叫圖靈完備的。一個能計算出每個圖靈可計算函數的計算系統被稱為圖靈完備的。一個語言是圖靈完備的，意味著該語言的計算能力與一個通用圖靈機相當，這也是現代計算機語言所能擁有的最高能力。

在可計算理論中，當一組數據操作的規則滿足任意數據按照一定的順序可以計算出結果，被稱為圖靈完備。一個有圖靈完備指令集的設備被定義為通用計算機。如果是圖靈完備的，它有能力執行條件跳轉以及改變內存數據。如果某個東西展現出了圖靈完備，它就有能力表現出可以模擬原始計算機，而即使最簡單的計算機也能模擬出最復雜的計算機。所有的通用編程語言和現代計算機的指令集都是圖靈完備的，都能解決內存有限的問題。圖靈完備的機器都被定義有無限內存，但是機器指令集卻通常定義為只工作在特定的，有限數量的RAM上。

動態 | 浙江衛視節目科普支付寶區塊鏈防偽溯源產品:昨日，在浙江衛視播出的科普綜藝欄目《智造將來》現場，支付寶首次展示了支付寶區塊鏈防偽溯源產品，以接地氣的方式公開向大眾展示區塊鏈在生活中的應用。[2019/3/4]

圖靈等價：我們可能經常會在某些文章里面看到圖靈等價和圖靈完備(Turingcompleteness)，但是這兩個詞的含義是有區別的。尤其是很多書或文章經常對這兩個詞進行混用，可能會把事情搞復雜。

在可計算理論里，一個數據操作規則的系統被稱作圖靈完備或者通用計算的，當且僅當它可以被用來模擬單帶圖靈機。在可計算理論里，有一個很相關的概念叫圖靈等價。當計算機P和計算機Q是圖靈等價的，P可以模擬Q而且Q也可以模擬P。現實中，一個圖靈完備的系統可以模擬圖靈機，這個術語常常被用來指與圖靈機等價。

所以一個圖靈完備的系統可以被稱為圖靈等價的，如果任何它可以計算的函數也是圖靈可計算的。也就是它可計算的函數和圖靈機可計算的函數是完全相同的。換句話說，就是圖靈等價的系統就是能模擬通用圖靈機同時也能也被通用圖靈機模擬的系統，所有已知的圖靈完備的系統都是圖靈等價的。

通過上面的分析，我們就可以清楚的知道這兩個詞的意思和關系了。圖靈等價有兩個意思，一個是指兩個計算系統在可計算性上計算能力相同；另一個，也是常用的一個就是指一個系統的計算能力與通用圖靈機計算能力相同。而圖靈完備是指能夠模擬通用圖靈機的計算系統。而所有已知的圖靈完備的系統都是圖靈等價的，這也增加了對丘奇-圖靈論題的支持。因此，就簡單的理解來說，在現有的計算機系統上，使用圖靈等價和圖靈完備是一個意思。

金色財經獨家分析 監管機構、媒體、業界提示詐騙風險 區塊鏈科普道阻且長:新華社今日發文表示，近來“區塊鏈”類詐騙案件頻發，不法分子以“投資虛擬貨幣周期短、收益高、風險低”為借口，騙取用戶信任并誘使其轉賬進行投資。無獨有偶，同日消息，騰訊手機管家安全專家也提醒此類風險，并從技術上提出防騙建議。在美國，監管機構警示加密貨幣欺詐現象普遍承諾高收益而不披露潛在風險。金色財經獨家分析，不法分子假借新技術之名進行詐騙，一方面是抓住民眾趨利的心理，一方面反映出區塊鏈科普的欠缺。區塊鏈是新興科技和底層技術并有改變社會生產關系的潛力，應該進行系統性的科普教育，當前，部分大學已經開始設置了區塊鏈課程，但對于普通民眾仍然有科普的需求，人們應該了解到系統和正確的知識，不僅要了解區塊鏈的好，也要明確局限和弊端，以在高收益的誘惑下，保持清醒客觀。[2018/4/11]

3.圖靈機

1935年，一個夏天。英國劍橋郁郁蔥蔥，23歲的圖靈在此讀書。這位年輕人性格內向，做人偏執，還是一名天賦異稟的馬拉松跑者。他的馬拉松最好成績是2小時46分，還差點代表英國國家隊參加奧運會。某次長跑后，圖靈癱倒在草地上，大口呼吸著劍橋的空氣，心跳逐漸平復，腦中卻出現了一場風暴。他一躍而起，跑回宿舍，在狂熱的心跳中寫下了腦中的風暴。他假想出一臺“圖靈機”：它可以從一條紙帶上讀取命令、進行操作，從而模擬任何“明確程序”。

他進一步證明人們可以設計出通用圖靈機，模擬任何圖靈機的運作，然后他進一步證明了即便通用圖靈機也無法讓所有命題可判斷——我們不能用一個算法來判定一臺給定的圖靈機是否會停機。

財政部副部長朱光耀：數字經濟還處在發展的過程中，要以科普、推動的態度來推進數字經濟發展:今日，在中國發展高層論壇2018年會上，財政部副部長朱光耀表示：“數字經濟還處在發展的過程中，要以科普、推動的態度來推進數字經濟發展。也要關注數字經濟的其他影響，包括稅收征管、反洗錢監管措施等要跟上。”[2018/3/25]

圖靈機的整個構造是一場思想實驗。它用紙筆和頭腦完成，不是一臺真的機器——在圖靈證明了存在通用圖靈機后的十來年，第一臺可編程的計算機被建造出來了。圖靈機后來成為整個電子計算機的藍圖。

圖靈機理論示意圖在第二次世界大戰中，他加入了英國絕密的破解德軍謎團密碼計劃。在圖靈的領導下，秘密工作小組幾乎破解了所有使用謎團密碼的情報，構成二戰轉折點，成為戰勝納粹的重要因素。

戰后，圖靈的興趣又回到他腦中的世界。這位天才科學家繼續著他純粹意義上的頭腦風暴——用思考，而不是手，去實現不完美世界中“可以自行迭代的機器”。如今的互聯網、人工智能與整個計算機世界，和彼時圖靈的設想高度吻合。

設想一下，我們在計算乘法的時候：在每個時刻，我們只將注意力集中在一個地方，根據已經讀到的信息移動筆尖，在紙上寫下符號或數字；而指示我們寫什么怎么寫的，則是早已背好的九九乘法表，以及簡單的加法。

參考維基百科中圖靈機的基本思想：圖靈的基本思想是用機器來模擬人們用紙筆進行數學運算的過程，他把這樣的過程看作下列兩種簡單的動作：在紙上寫上或擦除某個符號；把注意力從紙的一個位置移動到另一個位置；而在每個階段，人要決定下一步的動作，依賴于此人當前所關注的紙上某個位置的符號和此人當前思維的狀態。

圖靈機的實現結構并不復雜，它有一條無限長的紙帶，紙帶由方格組成。有一個讀寫頭在紙帶上移來移去，讀寫頭連接控制器，控制器內有狀態轉移表，還有一些固定的程序。在每個時刻，讀寫頭都要從當前紙帶上讀入一個方格信息，然后結合自己的內部狀態查找程序表，根據程序輸出信息到紙帶方格上，并轉換自己的內部狀態，然后進行移動。圖靈機不斷重復上述的步驟，這便是執行的過程。

4.圖靈測試

1950年，圖靈發表了題為《機器能思考嗎》的論文，在論文里提出了著名的“圖靈測試”。論文的開篇是一條明確的聲明：“我準備探討‘機器能思考嗎’這個問題。”然后，童心未泯的圖靈設計了一個游戲來解釋這個問題的實證含義。他為人工智能給出了一個完全可操作的定義：如果一臺機器輸出的內容和人類大腦別無二致的話，那么我們就沒有理由堅持認為這臺機器不是在“思考”。這就是“人工智能”的最初設想，這份設想也在無形中讓圖靈摘得了“人工智能之父”的桂冠。

圖靈測試圖靈測試，也就是圖靈所說的“模仿游戲”的操作很簡單：一位詢問者將自己的問題寫下來，發給處于另外一個房間之中的一個人和一臺機器，然后根據他們給出的答案確定哪個是真人。

至于何時會出現能夠通過圖靈測試的計算機，圖靈給出了自己的預測：“我相信在50年左右的時間內，計算機編程技術將可能……實現順利通過模仿游戲的計算機，普通詢問者在經過5分鐘的詢問之后的判斷準確率將不高于70%。”

圖靈預想到自己對思考的定義將會引來許多質疑，所以他嘗試在論文中逐一反駁它們。針對來自神學方面的質疑，也就是上帝只將靈魂和思考能力賜給了人類，圖靈表示這種觀點實際上是對“上帝的全知全能的嚴重限制”。他提出了一個問題：上帝是否“有自由向一頭合適的大象授予靈魂”？想必他是可以這樣做的，那么按照同樣的邏輯，上帝當然也可以隨心所欲地向一臺機器授予靈魂。這番話從不信仰上帝的圖靈口中說出還是有些諷刺意味的。

在《計算機器與智能》發表之后的幾年時間里，圖靈似乎很喜歡參與到自己惹出的爭論當中。他以自己帶有諷刺性的幽默感取笑了那些關人類高等意識的主張：“終有一天，女士們會帶著她們的計算機到公園散步，并且互相訴說“我的寶貝計算機在今天早上跟我說了這么一件有趣的事情”！智能手機是不是完全是這種預測？

5.圖靈獎

圖靈獎杯圖靈獎，由美國計算機協會(ACM)于1966年設立，有“計算機界諾貝爾獎”之稱。獎杯是一個銀色的碗。

從1966年到2019年，圖靈獎已經走過了半個多世紀，這也是計算機科學走過的半個世紀，獲獎成果串連起來，就是一部計算機科學史。這條旅途跌宕起伏，光影變幻，人類歷史上從沒有過哪個學科，在破殼而出后的短短半個世紀里推進如此之遠。圖靈獎的獎金設獎初期為20萬美元，1989年起增到25萬美元，獎金通常由計算機界的一些大企業提供。目前圖靈獎由Google公司贊助，獎金為100萬美元。

對于每一個行業和領域來說，幾乎都存在一兩項令其領域內所有人視為“終極榮譽”的大獎，例如電影業的奧斯卡獎、新聞領域的普利策獎，數學領域的沃爾夫獎和費爾茲獎等等。而在計算機行業，圖靈獎則是當之無愧的最高獎項。

從1966年頒發圖靈獎至今，已有50多個年頭，共授予了70位科學家。據相關資料統計，截止2018年，美國斯坦福大學的圖靈獎人數(校友或教職工)位列世界第一，美國麻省理工學院、美國加州大學伯克利分校并列世界第二；哈佛大學和普林斯頓大學分列世界第四和第五名。其中美國學者最多，此外還有英國、瑞士、荷蘭、以色列、挪威等國少數學者。

華人學者目前僅有2000年圖靈獎得主姚期智一人。

姚期智，1946年出生于中國上海，計算機學家，2000年圖靈獎獲得者，美國國家科學院院士、美國藝術與科學學院院士、中國科學院院士、港科院創院院士，清華大學高等研究中心教授，香港中文大學計算機科學與工程學系教授，清華大學-麻省理工學院-香港中文大學理論計算機科學研究中心主任，清華大學金融科技研究院管委會主任。他的主要貢獻領域為計算理論，包括偽隨機數生成，密碼學與通信復雜性。

圖靈是現代計算機設計思想的創始人，對計算機的貢獻杰出！

參考文獻：

安德魯·霍齊斯著，孫天齊譯，《艾倫·圖靈傳》2017年10月

Tags：區塊鏈人工智能比特幣ING區塊鏈的未來發展前景怎么樣人工智能幣種有哪些特比特幣鬧鬧什么歌BINGO幣

Luna