區塊鏈的圖靈完備

閱讀時間約 9 分鐘
摘要
圖靈於 1912 年在倫敦出生,1936 年 5 月,圖靈提交影響深遠的論文,讓通用圖靈機能模擬人的思考方式,最後,成為人工智慧之父。以太坊的「智能型合約」語言是運用圖靈完備,而圖靈完備的程式語言可以實現所有以前一個程式語言在單機上實現的功能,也即能盡最大限度滿足現實應用場景的開發。
keyword:通用圖靈機描述數、嘅演算法、停機問題、智能型合約
圖靈完備,圖靈完全性通常指具有無限存儲能力的通用物理機器或程式語言。圖靈完備意味著你的語言可以做到能夠用圖靈機能做到的所有事情,可以解決所有的可計算問題。
圖靈機的發明者:圖靈
圖靈(Turing)於 1912 年在倫敦出生,到了中學就長得高大壯碩,還是長跑健將。Christopher Morcom。他因為感染肺結核,身體嬴弱削瘦,但課業名列前茅,與圖靈一樣對數學、科學有極高的興趣,兩人常一起討論而成為莫逆之交。
無奈Morcom在畢業前一年不敵病魔而過世,用情至深的圖靈深受打擊,卻也因此更加專注於學業。圖靈如此努力的背後還有個重要動力。Morcom原本已經獲得劍橋大學的獎學金,圖靈想替他實現未能完成的人生,以進入劍橋大學為目標,最後圖靈也如願於 1931 年入學就讀。
圖靈無意打造一台真正的機器,因為他要處理的是抽象的原則性問題,重點在於思辨過程,而不是加減乘除。因此圖靈只須設想這台自動機器如何運作,無需考慮它如何製造。事實上這台後來以他為名的「圖靈機」極為簡化,硬體組成只有一個可以左右移動的讀寫頭,以及一條無限長的紙帶。與其說它是計算機,反倒比較像是台打字機。
圖靈機(Turing machine)
圖靈機(Turing machine)就是指一個抽象的機器,它有一條無限長的紙帶,紙帶分成了一個一個的小方格,每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內部狀態,還有一些固定的程序。在每個時刻,機器頭都要從當前紙帶上讀入一個方格信息,然後結合自己的內部狀態查找程序表,根據程序輸出信息到紙帶方格上,並轉換自己的內部狀態,然後進行移動。
這些影響讀寫頭與機器狀態的規則可以整理成一張「行為表」,例如,狀態:1,掃描結果—空白,向右移動,塗改方格不改,狀態不變;掃描結果—1,向右移動,塗改方格不改,狀態改為2。狀態:2,掃描結果—空白,向右移動,塗改方格寫上「1」,狀態改為3;掃描結果—不變,向右移動,塗改方格不改,狀態不變。
狀態:3,掃描結果—空白,向左移動,塗改方格不改,狀態改為4;掃描結果—1,向右移動,塗改方格不改,狀態不變。狀態:4,掃描結果—空白,不動,塗改方格不改,狀態不變;掃描結果—1,不動,塗改方格抹去「1」,狀態不變。
圖靈機只能從紙帶上讀取資料,所以行為表得用一行符號來表達,才能印在紙帶上讓圖靈機掃描。例如上面那張行為表可能就會變成一行指令:10RNN;11RN2;20R13;21RNN;30LN4;31RNN;40NNN;41N0N。
接著我們把指令中的英文字母與符號用數字代替,例如 A ~ Z 改為 11 ~ 33,分號”;” = 99,數字也跟著改用兩位數 00 ~ 09表示。如此一來,指令就會化為一串數字,圖靈稱之為「描述數」,意指這行純數字的數列就能描述圖靈機的行為。
正常的描述數可以讓圖靈機經過有限步驟後停下來,產生可計算數。但某些描述數卻可能讓圖靈機中途動彈不得,或是不斷來回繞圈圈,無法產生有意義的答案。例如「讀到 1 就往右;讀到 0 則往左」這個指令,就會讓圖靈機遇到 “1”、”0”相鄰時左右來回,永不停止(這其實就相當於「說謊者悖論」)。
如果一台圖靈機只有一個描述數,我們當然可以輕易地發現某台圖靈機停不下來,從而知道這個描述數有問題。不過實際上不需要建造那麼多台圖靈機。想像有台特別的「通用圖靈機」(圖靈稱之為 ”Universal machine“),可以把其它圖靈機的描述數都掃描進來,那麼它便能模擬任何一台圖靈機的運作。而且描述數除了代表運作規則,也可以當成數字做為編號,按大小順序排列,方便圖靈機搜尋。
圖靈完備的程式語言
圖靈機模型描述的是一個計算程序,它可以像物理的電腦一樣運作,完成一個電腦所能做的所有事情而所謂圖靈完備的程式語言,即是能夠實現所有計算機可以實現的功能的程式語言。
一台圖靈機個讀取器都會位於條帶其中一格,而部機會做以下三個基本作業當中是但一個:第一,讀取讀取器下嗰格係乜符號;第二,編輯嗰格-寫一個新嘅符號落去或者刪除咗嗰格佢;第三,將條帶向左或者向右移一格,等個讀取器可以讀取打前嗰個格隔離嘅一個格。
例如:圖靈機計算加減法。想像以下嘅演算法,條帶上面有兩個數值, x 和 y ,兩個都用二進制表達,而兩個數之間同條帶嘅起始有個 $ 做標示,是指部圖靈機會讀嘅輸入會類似噉嘅樣:$0010$0011(「0010」是二進制係 2,而「0011」是二進制係 3)。部機行完一次段演算法之後,條帶嘅狀態就會變成 $0000$0101(「0101」喺二進制入面係 5)
再想像一部圖靈機跟以下嘅演算法行:
// 由 x 嗰度減 1,再加 1 落 y 嗰度,直至 x = 0 為止。
repeat until x == 0, then HALT {
// 用 T2(睇下面)
subtract 1 from x
// 用 T1(睇下面)
add 1 to y
go back to the first $
}
說明如下:
T2(將個數減 1)如下:
補充-將 1 變做 0,0 變做 1;
將個數加 1(睇 T1);
再做一次補充。
T1(將個數加 1)如下:
如果喺個數嘅左邊盡頭($)起始,行去個數嘅右邊盡頭;
由右邊開始行,將所有 1 變做 0,直至
將第一個 0 變成 1
一般來講,我們平常使用的計算機程式語言,比如C、GO、爪哇都是圖靈完備的,因為它們都可以最大限度發揮計算機的能力。這些都是單機的情況,而在分布式下的情況如何呢?很顯然,在單機的情況下,實現所需要的功能是主要目的,而在分布式情況下如何解決上圖中的不一致的問題才是最關鍵的考量。
停機問題
圖靈完備語言最顯著的一個特點是支持循環,所謂循環,就是程序能不斷執行下去。那麼在區塊鏈支撐的分布式環境下,礦工如何判斷一個程序何時結束呢?而圖靈計算理論,也有人證明過,要證明一個程序能不能終止是不可能的(圖靈停機問題),所以這種「智能型合約」語言需要保證所寫出的程序不能存在死循環。
這也是為什麼以太坊語言會加入 GAS 氣體(瓦斯)的原因,通過加入氣體,程序每個運算過程都會消耗一定成本,從而不會無限制地執行下去。圖靈完備的智能合約相信在不久的將來可以實現更多、更複雜的去中心化的功能。不過,合約制定者不需要擔心防衞類似攻擊,因為如果執行中途停止則所有更改將被恢復。
計算機能模擬人的思考方式
1936 年 5 月,圖靈提交這篇影響深遠的論文:《論可計算數及其在判定性問題上的應用》 (On Computable Numbers, with an Application to the Entscheidungsproblem),不但在數學上占有重要地位,更展示許多計算機的創新設計。
他率先提出通用計算機的概念,將不同程式預先載入後再開始運行。而程式轉化為描述數,使得程式和資料共用同一個載體,也是首創。同時描述數做為程式的獨特編號,就相當於電腦程式在記憶體中的貯存位址;許多人相信這個概念啟發了馮紐曼用於 ENIAC 的設計。
圖靈還揭示了常人所未見的計算機角色。計算機的作用向來純粹就只為數學計算,但圖靈在這篇論文中卻是從人類如何思考的角度,討論如何讓機器模仿計算者的心智狀態。多年之後,圖靈提出「圖靈測試」,因而被稱為「人工智慧之父」。
以太坊的智能型合約
我們知道,比特幣誕生之後,大家逐漸發現了其底層的區塊鏈技術的巨大價值,同時認為區塊鏈技術才是分布式環境下解決這種一致性問題,可信的技術體系。這種分布式環境下實現一致性的語言現在都被統稱為「智能型合約」。比特幣腳本語言就是這樣一種語言,它實現了非常安全的數位貨幣計算模型,保證了在不需要第三方機構的情況下,兩方之間可以進行價值的轉移。
但是,現實世界的需求是極其龐雜的,為了滿足未來將區塊鏈技術應用於更多場景的可能需要,比特幣腳本語言是遠遠不夠的。這也是為什麼以以太坊為代表的區塊鏈技術,都宣稱自己所採用的「智能型合約」語言是圖靈完備的主要原因。
所以以太坊朝著這個目標在前進,也正是由於這個平台的強大,目前基於以太坊開發的區塊鏈應用越來越多。為什麼呢?通過上面的介紹就知道,以太坊的「智能型合約」語言是圖靈完備的,而圖靈完備的程式語言可以實現所有以前一個程式語言在單機上實現的功能,也即能盡最大限度滿足現實應用場景的開發。
為什麼會看到廣告
    avatar-img
    3會員
    46內容數
    類神經網路模型是運用數學、程式設計、心理學等知識的工具結構,它模仿神經元的節點,在功能上滿足了心理學研究泛用型神經網路(例如大腦)的彈性需求。要達到「使用者為中心的系統設計」目標,再以「認知工程」為手法,應用認知心理學的原理、原則於系統設計,使得機器人的功能和結構能夠與使用者的認知能力和心智模型相匹配,才能有用、能用。
    留言0
    查看全部
    avatar-img
    發表第一個留言支持創作者!
    Jeadre的沙龍 的其他內容
    元宇宙(metaverse)未來是虛無縹緲呢?還是,其希望指日可待?
    常常陪父親在家附近逛逛,培養與他的新感情;換個環境,務必解除他內心的焦慮;照護父親,需要愛,更需要方法與支援;搬進養護中心,從家中帶來對父親具有紀念意義的物品、照片、繪畫或個人創作物等等,來創造他對「新家」的依附;頻死階段而減少進食時,會尊重病人意願決定是否放置鼻胃管;生命末期、發生感染不用抗生素
    我們不該把失智者當成單方面需要照顧的人,而是營造『就算自己得了失智症,依然能過自己所期望的生活』的社會環境。失智不是死刑!請不要過度照顧失智者,給他們一個努力的機會。
    預防失智症必須了解病因、病程、治療方式,但,對於失智症長者之陪伴,確實相當重要。將失智症長輩當作成人對待:將失智症長輩當作成人對待、理解長輩情況,多些同理心。失智症照護指南包含懷舊回憶、認知活動、現實感知、營養照護、保持耐心等。
    瞭解區塊鏈在遊戲中扮演了打開投資交易的大門、結合NFT具有投資價值、邊玩還能賺錢的Play-to-Earn新模式等角色,但當它是一個金融商品,具有投資意義,政府的監管將會是最大的潛在風險。
    睡得好才排得掉大腦毒素;每天攝取一湯匙的蜂蜜,並且認真刷牙,LPS數量成功的減少,有益於睡眠;以及鍛鍊肌肉,降低打鼾、傷害大腦風險。
    元宇宙(metaverse)未來是虛無縹緲呢?還是,其希望指日可待?
    常常陪父親在家附近逛逛,培養與他的新感情;換個環境,務必解除他內心的焦慮;照護父親,需要愛,更需要方法與支援;搬進養護中心,從家中帶來對父親具有紀念意義的物品、照片、繪畫或個人創作物等等,來創造他對「新家」的依附;頻死階段而減少進食時,會尊重病人意願決定是否放置鼻胃管;生命末期、發生感染不用抗生素
    我們不該把失智者當成單方面需要照顧的人,而是營造『就算自己得了失智症,依然能過自己所期望的生活』的社會環境。失智不是死刑!請不要過度照顧失智者,給他們一個努力的機會。
    預防失智症必須了解病因、病程、治療方式,但,對於失智症長者之陪伴,確實相當重要。將失智症長輩當作成人對待:將失智症長輩當作成人對待、理解長輩情況,多些同理心。失智症照護指南包含懷舊回憶、認知活動、現實感知、營養照護、保持耐心等。
    瞭解區塊鏈在遊戲中扮演了打開投資交易的大門、結合NFT具有投資價值、邊玩還能賺錢的Play-to-Earn新模式等角色,但當它是一個金融商品,具有投資意義,政府的監管將會是最大的潛在風險。
    睡得好才排得掉大腦毒素;每天攝取一湯匙的蜂蜜,並且認真刷牙,LPS數量成功的減少,有益於睡眠;以及鍛鍊肌肉,降低打鼾、傷害大腦風險。
    你可能也想看
    Google News 追蹤
    Thumbnail
    這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
    Thumbnail
    11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
    Thumbnail
    Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
    Thumbnail
    ●智能合約 : 區塊2.0的產物   智能合約(Smart Contracts)最早是在1994年由Nick Szabo提出的概念,但一直到2015年,以太坊的創辦人Vitalik Buterin推出了智能合約,並運行於以太坊上,至今以太坊仍是最多人使用的智能合約區塊鏈。   ●智能
    Thumbnail
    ■什麼是區塊鏈技術? 區塊鏈是透過點對點(P2P)運行的網路,這個網路由分散式節點組成,可以把它想成是共享的數據庫,也就是分散式帳本(DLT),分散式帳本技術是一種去中心化的帳本,儲存著網路上進行的所有交易。 中心化帳本:也稱為集中式帳本,由一個中心化的機構去做驗證、記帳、訂立規則。
    Thumbnail
    AA、zkp、LSDFi 和 RWA 等區塊鏈技術和應用在2023年鬧的沸沸揚揚,前面我們已經介紹了何謂 RWA 以及 RWA 在 Cardano 鏈上的實際應用,今天這期我要來介紹 AA 錢包以及它背後的技術組成和未來發展。在本文中,我們將探討AA錢包的技術構成、現有問題和未來的發展方向。
    Thumbnail
    我們在前面幾篇介紹了區塊鏈的運作以及能在區塊鏈做的事情,這兩篇其實只是非常基礎且初淺的介紹,但區塊鏈最快的學習方式除了找人帶之外,在實戰中學習也是非常好的方式,作者本人也是透過直接實戰來強迫自己累積經驗,由於我剛接觸的時候也對於到底如何"進圈"充滿著疑問,所以這篇就來教大家如何踏入區塊鏈世界
    Thumbnail
    6種共識機制介紹,包含PoW、PoS、DPoS、PoA、PoC及PoUW
    Thumbnail
    在2018年時,好多人都不知道Bitcoin是什麼,很多人都懷疑Bitcoin是可一個龐氏騙局。但去到2021年,已經好少人會說是騙局,反而多了人討論除了Bitcoin,哪一個Crypto是更好的選擇,哪一個可以真正做到ETH Killer。今次的分享就是要講究竟有甚麼準則去衡量一個區塊鏈及加密貨幣
    Thumbnail
    本篇會聚焦分析成長股板塊內部的狀況,包括調整來到甚麼階段了?現在價格合理了嗎?成長股本身也有不同的板塊,各自情況如何?還會分享我個人應對這類大幅波動的投資心法,以及對持股的最新看法。
    Thumbnail
    其實區塊鏈發展至今,主要特點在於它具備了兩項特性,首先可先從區塊鏈這兩項特性著手了解,第一為區塊鏈具有不可竄改特性,而第二則為區塊鏈是一個去中心化的系統,這兩項特點賦予了區塊鏈在
    Thumbnail
    ​ 首先說明:這篇不是寫食記,而是一篇關於食品業一家股票上市公司。此家就是德麥食品公司(英文名稱:THEMAG       FOOD      CPMPANY),這是一家致力於人類民以食為天以食品為本業,身為台灣最大烘焙原物料供應商,十足之戰戰兢兢經營的企業。身為讀者的你,看完本文後一定會覺得;德麥
    Thumbnail
    這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
    Thumbnail
    11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
    Thumbnail
    Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
    Thumbnail
    ●智能合約 : 區塊2.0的產物   智能合約(Smart Contracts)最早是在1994年由Nick Szabo提出的概念,但一直到2015年,以太坊的創辦人Vitalik Buterin推出了智能合約,並運行於以太坊上,至今以太坊仍是最多人使用的智能合約區塊鏈。   ●智能
    Thumbnail
    ■什麼是區塊鏈技術? 區塊鏈是透過點對點(P2P)運行的網路,這個網路由分散式節點組成,可以把它想成是共享的數據庫,也就是分散式帳本(DLT),分散式帳本技術是一種去中心化的帳本,儲存著網路上進行的所有交易。 中心化帳本:也稱為集中式帳本,由一個中心化的機構去做驗證、記帳、訂立規則。
    Thumbnail
    AA、zkp、LSDFi 和 RWA 等區塊鏈技術和應用在2023年鬧的沸沸揚揚,前面我們已經介紹了何謂 RWA 以及 RWA 在 Cardano 鏈上的實際應用,今天這期我要來介紹 AA 錢包以及它背後的技術組成和未來發展。在本文中,我們將探討AA錢包的技術構成、現有問題和未來的發展方向。
    Thumbnail
    我們在前面幾篇介紹了區塊鏈的運作以及能在區塊鏈做的事情,這兩篇其實只是非常基礎且初淺的介紹,但區塊鏈最快的學習方式除了找人帶之外,在實戰中學習也是非常好的方式,作者本人也是透過直接實戰來強迫自己累積經驗,由於我剛接觸的時候也對於到底如何"進圈"充滿著疑問,所以這篇就來教大家如何踏入區塊鏈世界
    Thumbnail
    6種共識機制介紹,包含PoW、PoS、DPoS、PoA、PoC及PoUW
    Thumbnail
    在2018年時,好多人都不知道Bitcoin是什麼,很多人都懷疑Bitcoin是可一個龐氏騙局。但去到2021年,已經好少人會說是騙局,反而多了人討論除了Bitcoin,哪一個Crypto是更好的選擇,哪一個可以真正做到ETH Killer。今次的分享就是要講究竟有甚麼準則去衡量一個區塊鏈及加密貨幣
    Thumbnail
    本篇會聚焦分析成長股板塊內部的狀況,包括調整來到甚麼階段了?現在價格合理了嗎?成長股本身也有不同的板塊,各自情況如何?還會分享我個人應對這類大幅波動的投資心法,以及對持股的最新看法。
    Thumbnail
    其實區塊鏈發展至今,主要特點在於它具備了兩項特性,首先可先從區塊鏈這兩項特性著手了解,第一為區塊鏈具有不可竄改特性,而第二則為區塊鏈是一個去中心化的系統,這兩項特點賦予了區塊鏈在
    Thumbnail
    ​ 首先說明:這篇不是寫食記,而是一篇關於食品業一家股票上市公司。此家就是德麥食品公司(英文名稱:THEMAG       FOOD      CPMPANY),這是一家致力於人類民以食為天以食品為本業,身為台灣最大烘焙原物料供應商,十足之戰戰兢兢經營的企業。身為讀者的你,看完本文後一定會覺得;德麥