0
| 本文作者： 我在思考中 | 2022-07-13 15:57 |
作者 | Lawrence C. Paulson
1950年10月，一篇題為“機(jī)器能思考嗎”的論文橫空出世。這篇論文中提出了一個(gè)令人細(xì)思極恐的測(cè)試，即在測(cè)試者與被測(cè)試者（一個(gè)真人和一臺(tái)機(jī)器）隔開的情況下，通過(guò)通訊裝置向被測(cè)試者隨意提問(wèn)，并讓測(cè)試者猜測(cè)與自己對(duì)話的對(duì)方到底是真人還是機(jī)器。
在多次測(cè)試后，如果機(jī)器能平均讓每個(gè)參與者做出超過(guò)30%的誤判，那么這臺(tái)機(jī)器就通過(guò)了測(cè)試，并被認(rèn)為具有人類智能。
人們第一次意識(shí)到機(jī)器人可能具備人類智能，便是從此開始。這個(gè)測(cè)試便是令千萬(wàn)科幻愛好者津津樂道的圖靈測(cè)試。這篇文章也為作者Alan Turing（艾倫·圖靈）贏得了「人工智能之父」的桂冠。
而人工智能之路，或者說(shuō)計(jì)算機(jī)發(fā)展史的源頭，是一篇圖靈在24歲時(shí)發(fā)表的論文。在這篇論文中，他給「可計(jì)算性」下了一個(gè)嚴(yán)格的數(shù)學(xué)定義，并提出著名的「圖靈機(jī)（Turing Machine）」的設(shè)想。圖靈機(jī)不是一種具體的機(jī)器，而是一種思想模型，可制造一種十分簡(jiǎn)單但運(yùn)算能力極強(qiáng)的計(jì)算裝置，用來(lái)計(jì)算所有能想象得到的可計(jì)算函數(shù)。
因?yàn)閳D靈發(fā)明了圖靈機(jī)，于是時(shí)不時(shí)便有人跳出來(lái)宣稱圖靈其實(shí)「發(fā)明了計(jì)算機(jī)」。然而，圖靈機(jī)與實(shí)際計(jì)算機(jī)器的設(shè)計(jì)并不相同。圖靈機(jī)甚至不是機(jī)器的抽象模型。事實(shí)證明（有圖靈言論為證），圖靈機(jī)是一個(gè)人在桌上的紙張上書寫的模型。那么，圖靈為什么要發(fā)明圖靈機(jī)，而圖靈機(jī)又將引領(lǐng)我們?nèi)ハ蚝畏剑?/span>
解答這些疑問(wèn)的最好辦法是把課本放到一邊，打開論文。如今，借閱一本1936年的期刊不需要填寫借閱卡，也不需要等上一個(gè)小時(shí)讓圖書管理員從藏書室取來(lái)，我們只需要手捧一杯麥芽威士忌，在家里輕松訪問(wèn)谷歌即可。我們要尋找的那篇圖靈論文如下：
論文中有一些錯(cuò)誤，但瑕不掩瑜。正如Joel David Hamkins所說(shuō)，圖靈將可計(jì)算實(shí)數(shù)（computable real numbers）定義為具有可計(jì)算的十進(jìn)制展開數(shù)，這實(shí)際上是行不通的，不過(guò)修正并不困難。
圖靈在標(biāo)題中就說(shuō)明了這篇論文的寫作意圖：“論可計(jì)算數(shù)及其在「判定問(wèn)題」中的應(yīng)用 ”。其中“Entscheidungsproblem（判定問(wèn)題）”詢問(wèn)是否存在一種有效技術(shù)來(lái)決定給定的一階邏輯公式有效，即在所有解釋中為真。
圖靈將他的想法展開如下:
……
“可計(jì)算數(shù)”簡(jiǎn)單說(shuō)來(lái)就是，其十進(jìn)制的表達(dá)用有限的手段可計(jì)算的實(shí)數(shù)。按照我的定義，如果一個(gè)數(shù)的十進(jìn)制的表達(dá)能被機(jī)器寫下來(lái)，那么這個(gè)數(shù)就是可計(jì)算的。
圖靈后續(xù)進(jìn)行了定義和證明，這是一篇典型的數(shù)學(xué)論文，而不是典型的工程論文，在這種文章里讀者想看到討論如何實(shí)現(xiàn)文中所描述的某種機(jī)制。從圖靈的標(biāo)題和文章中我們可以看出，圖靈主要關(guān)心的是一個(gè)實(shí)數(shù)到無(wú)限位小數(shù)的計(jì)算。
這篇論文還有許多其他重要貢獻(xiàn)：
通用圖靈機(jī)，以及以數(shù)字形式為機(jī)器編碼的想法
如此編碼的機(jī)器的停機(jī)問(wèn)題，以及對(duì)角化的不可判定性
寫罷這篇論文，圖靈打開了理論計(jì)算科學(xué)領(lǐng)域的大門。
我們不能確定是什么讓圖靈產(chǎn)生了通用圖靈機(jī)（UTM）的想法，但一旦他想到了，他可能會(huì)認(rèn)為通用圖靈機(jī)的存在是顯而易見的。因?yàn)閳D靈機(jī)的目的就是模擬一個(gè)在辦公桌上工作的職員，而圖靈機(jī)的操作和文員行為一樣——根據(jù)機(jī)器狀態(tài)和磁帶符號(hào)，根據(jù)給定的轉(zhuǎn)換規(guī)則列表執(zhí)行這個(gè)或那個(gè)操作——顯然需要一個(gè)圖靈機(jī)來(lái)執(zhí)行這樣的例行任務(wù)。圖靈的論文對(duì)于構(gòu)造的細(xì)節(jié)有些粗略，但似乎沒有人介意。
而如今，我們有了已經(jīng)被設(shè)計(jì)得淋漓盡致的通用圖靈機(jī)。幾十年前，在劍橋大學(xué)，Ken Moody 博士編寫了一個(gè)通用明斯基注冊(cè)機(jī)：
鏈接：http://www.igblan.free-online.co.uk/igblan/ca/minsky.html
這樣的機(jī)器有有限的寄存器，每個(gè)寄存器可以存儲(chǔ)任意大的非負(fù)整數(shù)。它有一個(gè)有限程序，由三種不同類型的標(biāo)記指令組成：
遞增寄存器R并跳到標(biāo)簽L，或R+→L
測(cè)試/遞減寄存器R并跳轉(zhuǎn)到標(biāo)簽L0/L1，或L0?R?→L1
中斷。
這樣的機(jī)器比圖靈機(jī)更容易編程，盡管它們?nèi)匀徊幌裾嬲挠?jì)算機(jī)。
Moody在N和N×N之間使用了標(biāo)準(zhǔn)的雙射，將整數(shù)列表打包成單個(gè)整數(shù)。他編寫了一個(gè)小型寄存器機(jī)器的小庫(kù)，用于執(zhí)行堆棧上推和從堆棧彈出等操作，并創(chuàng)建了一個(gè)讓人想起真實(shí)處理器的獲取-執(zhí)行周期的設(shè)計(jì)。整個(gè)過(guò)程可見以下幾張幻燈片。下圖是機(jī)器本身：
下圖則是機(jī)器的整體結(jié)構(gòu)。(這兩張圖的作者都是劍橋大學(xué)理論計(jì)算科學(xué)教授Andrew Pitts。)
出人意料的是，這個(gè)機(jī)器的結(jié)構(gòu)真簡(jiǎn)單！
停頓問(wèn)題顯然是不可決定的。否則，許多數(shù)學(xué)上的猜想都會(huì)難以解決，比如費(fèi)馬大定理：只要寫一個(gè)程序，搜索x, y, z, n>2，使
，并問(wèn)它是否終止。然而，停機(jī)的不可判定性必須被嚴(yán)格地表達(dá)和證明。
與大眾看法相反，圖靈的論文并沒有討論停機(jī)問(wèn)題，而是討論了一個(gè)與停機(jī)問(wèn)題相關(guān)的特性，他稱之為“循環(huán)性”（circularity）。如果圖靈機(jī)「只寫下有限數(shù)量的第一種符號(hào)」（即0和1），它就是循環(huán)性的。我想，循環(huán)性之所以重要，是因?yàn)閳D靈特別喜歡把實(shí)數(shù)近似為無(wú)限的二進(jìn)制字符串。物理學(xué)家Christopher Strachey在1965年給《計(jì)算機(jī)雜志（Computer Journal）》的一封信中聲稱，圖靈告訴他一個(gè)關(guān)于停機(jī)問(wèn)題不可判定性的證明。
2009年9月，David P. Anderson采訪了Maurice Wilkes，他對(duì)圖靈的看法卻與大眾恰恰相反：
Maurice Wilkes：我覺得一個(gè)工程師會(huì)把存儲(chǔ)程序（stored program）的想法當(dāng)成類似三位一體的重要理論，并會(huì)說(shuō)："這絕對(duì)是一流的，就應(yīng)該按這辦法做"。
那篇論文中的思想與我所說(shuō)的沒有任何具有實(shí)際意義的區(qū)別。他能發(fā)表那篇論文已經(jīng)很幸運(yùn)了， 我的意思是阿隆佐·邱奇（Alonzo Church）用其他方法得到了同樣的結(jié)果。
文章地址：https://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext
需要注意的是，在接受采訪時(shí)，Maurice Wilkes已經(jīng)96歲高齡了，他本人是著名的計(jì)算機(jī)先驅(qū)，EDSAC（Electronic Delay Storage Automatic Calculator，即電子延遲存儲(chǔ)自動(dòng)計(jì)算器）之父。在他這段奇怪的回答中，可以看出他對(duì)圖靈崇高地位的嫉妒。這兩個(gè)人顯然合不來(lái)！我們也看到了Maurice Wilkes對(duì)理論的不屑：盡管把機(jī)器編碼為數(shù)字是對(duì)存儲(chǔ)程序計(jì)算機(jī)的預(yù)期，但圖靈的工作是純粹的數(shù)學(xué)，沒有任何工程意義。圖靈對(duì)實(shí)際的計(jì)算機(jī)工程很感興趣，但他多次試圖參與到真正的工程里，卻屢屢受挫。
而那些關(guān)于邱奇的言論又是如何評(píng)價(jià)的呢?
在圖靈做研究的時(shí)候，許多研究人員關(guān)注的是“有效可計(jì)算性”的想法。此處我推薦讀者看看邱奇的《初等數(shù)論的一個(gè)不可解問(wèn)題》（見下圖）。
論文鏈接：https://www.jstor.org/stable/2371045?origin=crossref
老實(shí)說(shuō)，這篇論文讀起來(lái)很吃力，但它能帶我們身臨其境。本文給出了一個(gè)λ-演算的定義，一個(gè)遞歸函數(shù)的定義(在Kleene（克萊尼）/G?del（哥德爾）意義上)，以及λ-演算中范式的存在性和等價(jià)性的一些不可判定結(jié)果。邱奇和克萊尼已經(jīng)證明了λ可定義函數(shù)和遞歸函數(shù)的等價(jià)性；而當(dāng)圖靈在普林斯頓的時(shí)候，λ可定義函數(shù)和圖靈可計(jì)算函數(shù)之間的等價(jià)性也得到了證明，于是我們便得到了邱奇-圖靈論題，這個(gè)論題的指的是有效可計(jì)算的函數(shù)恰恰是那些數(shù)學(xué)上等價(jià)類中的函數(shù)。
正如人們常說(shuō)的那樣，我們無(wú)法證明這個(gè)論題正確與否，因?yàn)椤赣行Э捎?jì)算」不是一個(gè)精確的概念。我們可以把圖靈可計(jì)算函數(shù)看作是一個(gè)頗為包容的類，因?yàn)槠浒嗽S多在宇宙生命周期內(nèi)無(wú)法計(jì)算的函數(shù)。借助Ackermann函數(shù)，我們可以很容易地得到范例。
Ackermann函數(shù)的現(xiàn)代形式如下：
文章鏈接：https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html
如果你定義f(n)=A(n,n)，就不能指望計(jì)算出偶數(shù)f(4)。g(n)=A(4,n)盡管是原始遞歸，但幾乎無(wú)法計(jì)算。
盡管在20世紀(jì)30年代之前都還沒有數(shù)字計(jì)算機(jī)，但有效可計(jì)算性的概念已為數(shù)學(xué)家所熟知。有效性的概念在希臘幾何的直線結(jié)構(gòu)和圓規(guī)結(jié)構(gòu)中就早已出現(xiàn)，有效性也是判定問(wèn)題和希爾伯特第十問(wèn)題的組成部分。與哥德爾的遞歸函數(shù)和邱奇的λ微積分相比，圖靈的概念的天才之處在于其顯然是正確的。哥德爾自己也不確定他的遞歸函數(shù)是否抓住了計(jì)算的思想，我們也不清楚邱奇的想法是否正確。唯有圖靈的想法簡(jiǎn)單而自然。圖靈的想法與其他模型在可證明性上是等價(jià)的，并為所有這些模型提供了合理解釋。他在1937年發(fā)表的論文《可計(jì)算性和λ-可定義性》中指出了這一事實(shí)。
注意，圖靈寫的是「可計(jì)算的」，而我們要寫「圖靈可計(jì)算的」。
原文鏈接：
雷峰網(wǎng)(公眾號(hào)：雷峰網(wǎng))
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
