1950年10月,一篇題為「機器能思考嗎」的論文橫空出世。這篇論文中提出了一個令人細思極恐的測試,即在測試者與被測試者(一個真人和一台機器)隔開的情況下,透過通訊裝置向被測試者隨意提問,並讓測試者猜測與自己對話的對方到底是真人還是機器。
在多次測試後,如果機器能平均讓每個參與者做出超過30%的誤判,那麼這台機器就通過了測試,並被認為具有人類智能。
人們第一次意識到機器人可能具備人類智能,便是從此開始。這個測試便是令千萬科幻愛好者津津樂道的圖靈測試。這篇文章也為作者Alan Turing(艾倫·圖靈)贏得了「人工智慧之父」的桂冠。
而人工智慧之路,或者說電腦發展史的源頭,是一篇圖靈在24歲時發表的論文。在這篇論文中,他為「可計算性」下了一個嚴格的數學定義,並提出著名的「圖靈機(Turing Machine)」的設想。圖靈機不是一種具體的機器,而是一種思想模型,可製造一個十分簡單但運算能力極強的計算裝置,用來計算所有能想像得到的可計算函數。
因為圖靈發明了圖靈機,於是時不時便有人跳出來宣稱圖靈其實「發明了電腦」。然而,圖靈機與實際計算機器的設計並不相同。圖靈機甚至不是機器的抽像模型。事實證明(有圖靈言論為證),圖靈機是一個人在桌上的紙張上書寫的模型。那麼,圖靈為什麼要發明圖靈機,而圖靈機又將引領我們去向何方?
1 圖靈的論文「論可計算數」
#解答這些疑問的最好方法是把課本放到一邊,打開論文。如今,借閱一本1936年的期刊不需要填寫借閱卡,也不需要等上一個小時讓圖書館員從藏書室取來,我們只需要手捧一杯麥芽威士忌,在家裡輕鬆訪問谷歌即可。我們要找的那篇圖靈論文如下:
#論文網址:https://www.cs.virginia.edu/ ~robins/Turing_Paper_1936.pdf
#論文中有些錯誤,但瑕。正如Joel David Hamkins所說,圖靈將可計算實數(computable real numbers)定義為具有可計算的十進制展開數,這實際上是行不通的,不過修正並不困難。
圖靈在標題中就說明了這篇論文的寫作意圖:「論可計算數及其在「判定問題」中的應用」。其中「Entscheidungsproblem(判定問題)」詢問是否存在一種有效技術來決定給定的一階邏輯公式有效,即在所有解釋中為真。
圖靈將他的想法展開如下:
我們可以把一個正在計算實數的人比喻成一台只能滿足有限數量條件q1,q2,... qR...的機器。這台機器中有一條長長的「紙帶」穿過,紙帶被分成很多個部分,這種一塊一塊的部分我們將其稱為方塊(square),每個方塊都能承載一個「符號」...有些寫下的符號會形成被計算的實數的十進制的數字序列,而其他的符號則只是“幫助記憶”的粗略筆記。這些粗略的筆記是可以擦掉的。我的論點是,這種在紙帶上滑來滑去,滑到某個符號並對這個符號進行相應處理的運算方式,其中包括了所有用於數字計算的運算。
…
#「可計算數」簡單說來就是,其十進制的表達式用有限的手段可計算的實數。按照我的定義,如果一個數的十進制的表達能被機器寫下來,那麼這個數就是可計算的。
圖靈後續進行了定義和證明,這是一篇典型的數學論文,而不是典型的工程論文,在這種文章裡讀者想看到討論如何實現文中所描述的某種機制。從圖靈的標題和文章中我們可以看出,圖靈主要關心的是一個實數到無限位小數的計算。
#這篇論文還有許多其他重要貢獻:
- 通用圖靈機,以及以數位形式為機器編碼的想法
- #如此編碼的機器的停機問題,以及對角化的不可判定性
#寫罷這篇論文,圖靈打開了理論計算科學領域的大門。
2 通用圖靈機
我們不能確定是什麼讓圖靈產生了通用圖靈機(UTM)的想法,但一旦他想到了,他可能會認為通用圖靈機的存在是顯而易見的。因為圖靈機的目的是模擬一個在辦公桌上工作的職員,而圖靈機的操作和文員行為一樣——根據機器狀態和磁帶符號,根據給定的轉換規則列表執行這個或那個操作——顯然需要圖靈機來執行這樣的例行任務。圖靈的論文對於構造的細節有些粗略,但似乎沒有人介意。
而如今,我們有了已經被設計得淋漓盡致的通用圖靈機。幾十年前,在劍橋大學,Ken Moody 博士編寫了一個通用明斯基註冊機:
連結:http: //www.igblan.free-online.co.uk/igblan/ca/minsky.html
這樣的機器有有限的暫存器,每個暫存器可以儲存任意大的非負整數。它有一個有限程序,由三種不同類型的標記指令組成:
- 遞增暫存器R並跳轉到標籤L,或R →L
- 測試/遞減暫存器R並跳到標籤#L0/L1,或L0↞R−→#L1
- # #中斷。
這樣的機器比圖靈機更容易編程,儘管它們仍然不像真正的電腦。
Moody在N和N×N之間使用了標準的雙射,將整數清單打包成單一整數。他編寫了一個小型暫存器機器的小庫,用於執行堆疊上推和從堆疊彈出等操作,並創建了一個讓人想起真實處理器的獲取-執行週期的設計。整個過程可見以下幾張幻燈片。下圖是機器本身:
下圖則是機器的整體結構。 (這兩張圖的作者都是劍橋大學理論計算科學教授Andrew Pitts。)
#出乎意料的是,這個機器的結構真簡單!
3 停機問題
停頓問題顯然是無法決定的。否則,許多數學上的猜想都會難以解決,例如費馬大定理:只要寫一個程序,搜尋x, y, z, n>2,使,並問它是否終止。然而,停機的不可判定性必須嚴格表達和證明。
與大眾看法相反,圖靈的論文並沒有討論停機問題,而是討論了一個與停機問題相關的特性,他稱之為「循環性」(circularity)。如果圖靈機「只寫下有限數量的第一種符號」(即0和1),它就是循環性的。我想,循環性之所以重要,是因為圖靈特別喜歡把實數近似為無限的二進位字串。物理學家Christopher Strachey在1965年給《電腦雜誌(Computer Journal)》的一封信中聲稱,圖靈告訴他一個關於停機問題不可判定性的證明。
#
4 圖靈和Maurice Wilkes
2009年9月,David P. Anderson訪問了Maurice Wilkes,他對圖靈的看法卻與大眾恰恰相反:
David P. Anderson:你認為圖靈1936年所發表的判定問題論文的重要性何在?
Maurice Wilkes:我覺得一個工程師會把儲存程式(stored program)的想法當成類似三位一體的重要理論,並會說:「這絕對是一流的,就應該照這辦法做"。
那篇論文中的想法與我所說的沒有任何具有實際意義的區別。他能發表那篇論文已經很幸運了, 我的意思是阿隆佐·邱奇(Alonzo Church)用其他方法得到了同樣的結果。
文章網址:https://cacm.acm.org/magazines/2009/9/38898-an-interview-with -maurice-wilkes/fulltext
要注意的是,在接受採訪時,Maurice Wilkes已經96歲了,他本人是著名的電腦先驅,EDSAC(Electronic Delay Storage Automatic Calculator,即電子延遲儲存自動計算器)之父。在他這段奇怪的回答中,可以看出他對圖靈崇高地位的嫉妒。這兩個人顯然合不來!我們也看到了Maurice Wilkes對理論的不屑:儘管把機器編碼為數字是對儲存程式電腦的預期,但圖靈的工作是純粹的數學,沒有任何工程意義。圖靈對實際的電腦工程很感興趣,但他多次試圖參與真正的工程裡,卻屢屢受挫。
而那些關於邱奇的言論又是如何評價的呢?
#5 圖靈和邱奇在普林斯頓
在圖靈做研究的時候,許多研究人員關注的是「有效可計算性」的想法。這裡我推薦讀者看看邱奇的《初等數論的一個不可解問題》(見下圖)。
論文連結:https://www.jstor.org/stable/2371045?origin=crossref
#老實說,這篇論文讀起來很吃力,但它能帶我們身臨其境。本文給了一個λ-演算的定義,一個遞歸函數的定義(在Kleene(克萊尼)/Gödel(哥德爾)意義上),以及λ-演算中範式的存在性和等價性的一些不可判定結果。邱奇和克萊尼已經證明了λ可定義函數和遞歸函數的等價性;而當圖靈在普林斯頓的時候,λ可定義函數和圖靈可計算函數之間的等價性也得到了證明,於是我們便得到了邱奇-圖靈論題,這個論題的指的是有效可計算的函數恰恰是那些數學上等價類中的函數。
6 邱奇-圖靈論題正確嗎?
正如人們常說的那樣,我們無法證明這個論題正確與否,因為「有效可計算」不是一個精確的概念。我們可以把圖靈可計算函數看成是一個相當包容的類,因為其包括了許多在宇宙生命週期內無法計算的函數。借助Ackermann函數,我們可以很容易地得到範例。
Ackermann函數的現代形式如下:
文章連結:https:// lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html
##如果你定義f(n)=A(n,n),就不能指望計算出偶數f(4)。 g(n)=A(4,n)儘管是原始遞歸,但幾乎無法計算。
儘管在20世紀30年代之前都還沒有數位計算機,但有效可計算性的概念已為數學家所熟知。有效性的概念在希臘幾何的直線結構和圓規結構中就早已出現,有效性也是判定問題和希爾伯特第十問題的組成部分。與哥德爾的遞歸函數和邱奇的λ微積分相比,圖靈的概念的天才之處在於其顯然是正確的。哥德爾自己也不確定他的遞歸函數是否抓住了計算的思想,我們也不清楚邱奇的想法是否正確。唯有圖靈的想法簡單而自然。圖靈的想法與其他模型在可證明性上是等價的,並為所有這些模型提供了合理解釋。他在1937年發表的論文《可計算性和λ-可定義性》中指出了這一事實。
本文旨在證明作者提出的可計算函數與邱奇的λ-可定義函數以及由埃爾布朗和哥德爾所提出的並由克萊尼發展的一般遞歸函數是相同的。這幾個相同的函數都證明了每個X-定義函數都是可計算的,並且每個可計算函數都是一般遞歸的。
注意,圖靈寫的是「可計算的」,而我們要寫「圖靈可計算的」。
以上是圖靈機:在沒有計算機的時候,我們要如何談論計算?的詳細內容。更多資訊請關注PHP中文網其他相關文章!

Meta攜手Nvidia、IBM和Dell等合作夥伴,拓展了Llama Stack的企業級部署整合。在安全方面,Meta推出了Llama Guard 4、LlamaFirewall和CyberSecEval 4等新工具,並啟動了Llama Defenders計劃,以增強AI安全性。此外,Meta還向10個全球機構(包括致力於改善公共服務、醫療保健和教育的初創企業)發放了總額150萬美元的Llama Impact Grants。 由Llama 4驅動的全新Meta AI應用,被設想為Meta AI

公司開創性的人類互動公司Joi AI介紹了“ AI-Iatsionship”一詞來描述這些不斷發展的關係。 Joi AI的關係治療師Jaime Bronstein澄清說,這並不是要取代人類C

在線欺詐和機器人攻擊對企業構成了重大挑戰。 零售商與機器人ho積產品,銀行戰斗帳戶接管以及社交媒體平台與模仿者鬥爭。 AI的興起加劇了這個問題,Rende

AI代理人有望徹底改變營銷,並可能超過以前技術轉變的影響。 這些代理代表了生成AI的重大進步,不僅是處理諸如chatgpt之類的處理信息,而且還採取了Actio

人工智能對關鍵NBA遊戲4決策的影響 兩場關鍵遊戲4 NBA對決展示了AI在主持儀式中改變遊戲規則的角色。 首先,丹佛的尼古拉·喬基奇(Nikola Jokic)錯過了三分球,導致亞倫·戈登(Aaron Gordon)的最後一秒鐘。 索尼的鷹

傳統上,擴大重生醫學專業知識在全球範圍內要求廣泛的旅行,動手培訓和多年指導。 現在,AI正在改變這一景觀,克服地理局限性並通過EN加速進步

英特爾正努力使其製造工藝重回領先地位,同時努力吸引無晶圓廠半導體客戶在其晶圓廠製造芯片。為此,英特爾必須在業界建立更多信任,不僅要證明其工藝的競爭力,還要證明合作夥伴能夠以熟悉且成熟的工作流程、一致且高可靠性地製造芯片。今天我聽到的一切都讓我相信英特爾正在朝著這個目標前進。 新任首席執行官譚立柏的主題演講拉開了當天的序幕。譚立柏直率而簡潔。他概述了英特爾代工服務的若干挑戰,以及公司為應對這些挑戰、為英特爾代工服務的未來規劃成功路線而採取的措施。譚立柏談到了英特爾代工服務正在實施的流程,以更以客

全球專業再保險公司Chaucer Group和Armilla AI解決了圍繞AI風險的日益嚴重的問題,已聯手引入了新型的第三方責任(TPL)保險產品。 該政策保護業務不利


熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

DVWA
Damn Vulnerable Web App (DVWA) 是一個PHP/MySQL的Web應用程序,非常容易受到攻擊。它的主要目標是成為安全專業人員在合法環境中測試自己的技能和工具的輔助工具,幫助Web開發人員更好地理解保護網路應用程式的過程,並幫助教師/學生在課堂環境中教授/學習Web應用程式安全性。 DVWA的目標是透過簡單直接的介面練習一些最常見的Web漏洞,難度各不相同。請注意,該軟體中

Safe Exam Browser
Safe Exam Browser是一個安全的瀏覽器環境,安全地進行線上考試。該軟體將任何電腦變成一個安全的工作站。它控制對任何實用工具的訪問,並防止學生使用未經授權的資源。

SublimeText3 Linux新版
SublimeText3 Linux最新版

Dreamweaver CS6
視覺化網頁開發工具

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具