區(qū)塊鏈的圖靈機(jī)和圖靈完備是什么

本篇內(nèi)容主要講解“區(qū)塊鏈的圖靈機(jī)和圖靈完備是什么”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“區(qū)塊鏈的圖靈機(jī)和圖靈完備是什么”吧!

1圖靈機(jī)的組成

網(wǎng)上有一張經(jīng)典的圖片來(lái)表達(dá)圖靈機(jī)的構(gòu)成，圖如下：

這張圖片什么意思？這么一個(gè)簡(jiǎn)單的機(jī)器/裝置怎么會(huì)所有電子計(jì)算機(jī)的理論模型？

相信大家看到這張圖后都有這樣的疑問(wèn)，下面筆者帶來(lái)由淺入深去理解圖靈機(jī)的組成。

圖靈的基本思想是用機(jī)器來(lái)模擬人們用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程，它運(yùn)算過(guò)程看作下列兩種簡(jiǎn)單的動(dòng)作：

• 在紙上寫(xiě)上或擦除某個(gè)符號(hào)；

• 把注意力從紙的一個(gè)位置移動(dòng)到另一個(gè)位置；

邏輯結(jié)構(gòu)上圖靈機(jī)有四個(gè)部分組成：

• 一個(gè)無(wú)限長(zhǎng)的存儲(chǔ)帶，帶子有一個(gè)個(gè)連續(xù)的存儲(chǔ)格子組成，每個(gè)格子可以存儲(chǔ)一個(gè)數(shù)字或符號(hào)

• 一個(gè)讀寫(xiě)頭，讀寫(xiě)頭可以在存儲(chǔ)帶上左右移動(dòng)，并可以讀、修改存儲(chǔ)格上的數(shù)字或符號(hào)

• 內(nèi)部狀態(tài)存儲(chǔ)器，該存儲(chǔ)器可以記錄圖靈機(jī)的當(dāng)前狀態(tài)，并且有一種特殊狀態(tài)為停機(jī)狀態(tài)

• 控制程序指令，指令可以根據(jù)當(dāng)前狀態(tài)以及當(dāng)前讀寫(xiě)頭所指的格子上的符號(hào)來(lái)確定讀寫(xiě)頭下一步的動(dòng)作（左移還是右移），并改變狀態(tài)存儲(chǔ)器的值，令機(jī)器進(jìn)入一個(gè)新的狀態(tài)或保持狀態(tài)不變。

當(dāng)然這些只是理想的圖靈機(jī)，因?yàn)楝F(xiàn)實(shí)中不存在無(wú)限長(zhǎng)的存儲(chǔ)帶，更加圖靈的理論這樣的一臺(tái)裝置就能模擬人類(lèi)所能進(jìn)行的任何計(jì)算過(guò)程。是不是很神奇？我相信你肯定不相信，不過(guò)圖靈是經(jīng)過(guò)嚴(yán)格的數(shù)學(xué)證明，下面我們來(lái)看看圖靈機(jī)的計(jì)算過(guò)程。

2圖靈機(jī)的運(yùn)行機(jī)制

圖靈機(jī)工作步驟

準(zhǔn)備

• 存儲(chǔ)帶子上的格子初始話(huà)      

• 設(shè)置內(nèi)部狀態(tài)存儲(chǔ)器當(dāng)前狀態(tài)      

• 讀寫(xiě)頭設(shè)置初始在存儲(chǔ)帶上所做的格子位置      

• 準(zhǔn)備好控制指令，即控制程序。

反復(fù)執(zhí)行以下步驟，直到停機(jī)

• 讀寫(xiě)頭讀出當(dāng)前格子的數(shù)字或符號(hào) 

• 根據(jù)當(dāng)前狀態(tài)和讀到的字母或符號(hào)找到對(duì)應(yīng)的控制指令 

• 根據(jù)控制指令，執(zhí)行以下三個(gè)動(dòng)作   

  讀寫(xiě)頭在格子上擦除或?qū)懭胍粋€(gè)數(shù)字或符號(hào)   

  變更狀態(tài)到一個(gè)新?tīng)顟B(tài)     

  讀寫(xiě)頭向左或向右移動(dòng)一格

估計(jì)你還是不明白，別急?？催^(guò)《三體》的同學(xué)都知道三體人把地球人看做“蟲(chóng)子”，三體人的維度比地球三維世界高，就好像我們?nèi)祟?lèi)把看蟲(chóng)子一樣。

下面，我們把蟲(chóng)子放到一個(gè)二維的世界中，以蟲(chóng)子為例，給大家來(lái)說(shuō)明最簡(jiǎn)單的圖靈機(jī)模型（注：該例子非原創(chuàng)）。

假設(shè)理想的情況一：

• 蟲(chóng)子所處的二維世界是一個(gè)無(wú)限長(zhǎng)的紙帶，這個(gè)紙帶上被分成了若干小的方格，而每個(gè)方格都僅僅只有黑和白兩種顏色。紙帶的片段為：

蟲(chóng)子所在二維紙帶

• 假設(shè)蟲(chóng)子的感官只有眼睛，并且它的視力短的可憐，只能看到當(dāng)前所處格子的顏色

• 蟲(chóng)子可以向前爬一個(gè)格子或向后爬一個(gè)格子

• 蟲(chóng)子的操作系統(tǒng)、程序?yàn)椋何覀兗僭O(shè)黑色是食物區(qū)，蟲(chóng)子吃到食物后前移一格，白色是空白區(qū)，沒(méi)有食物后退一格，

在這個(gè)情況中格子的顏色是蟲(chóng)子的輸入信息，集合為IN={黑色，白色}，輸出集合為 OUT= {前移一格，后移一格}

從開(kāi)始位置開(kāi)始，蟲(chóng)子會(huì)怎么移動(dòng)呢？

• 開(kāi)始是黑色，蟲(chóng)子前移一格，到達(dá)第2格

• 第2還是黑色，蟲(chóng)子前移一格，到達(dá)第3格

• 第3格還是黑色，蟲(chóng)子前移一格，到達(dá)第4格

• 第4格為白色，蟲(chóng)子后移一格，回到第3格

• 可見(jiàn)，這條帶子上，蟲(chóng)子在第4格和第3格來(lái)回移動(dòng)循環(huán)不止。

假設(shè)理想的情況二

現(xiàn)實(shí)中蟲(chóng)子肯定不可能傻到無(wú)線(xiàn)循環(huán)，蟲(chóng)子會(huì)有饑餓、吃飽的感受，食物吃了后也會(huì)消失。因此我們?cè)谇闆r下中改進(jìn)下模型。

• 蟲(chóng)子在黑色的格子時(shí)，如果是饑餓狀態(tài)，吃掉食物把格子變成白色；如果是吃飽狀態(tài)，后移一格

• 蟲(chóng)子在白色的格子時(shí)，如果是饑餓狀態(tài)，停下來(lái)等食物長(zhǎng)出來(lái)涂黑；如果是吃飽狀態(tài)，前移一格

• 蟲(chóng)子的操作系統(tǒng)、程序?yàn)椋?/p>

在這種情況中，輸入集合為IN={黑色，白色}，輸出集合為 OUT= {前移一格，后移一格，吃掉食物涂白，等待食物長(zhǎng)出來(lái)涂黑}，內(nèi)部狀態(tài)S={吃飽，饑餓}

二維紙帶不變，從開(kāi)始位置開(kāi)始，蟲(chóng)子初始是饑餓狀態(tài)，蟲(chóng)子會(huì)怎么移動(dòng)呢？

• 第1格是黑色，蟲(chóng)子饑餓，吃掉食物格子變白，蟲(chóng)子新?tīng)顟B(tài)為吃飽

• 第1格為白色，蟲(chóng)子吃飽，蟲(chóng)子前移一格，到達(dá)第2格，蟲(chóng)子新?tīng)顟B(tài)為饑餓

• 第2格為黑色，蟲(chóng)子饑餓，吃掉食物格子變白，蟲(chóng)子新?tīng)顟B(tài)為吃飽

• 第2格為白色，蟲(chóng)子吃飽，蟲(chóng)子前移一格，到達(dá)第3格，蟲(chóng)子新?tīng)顟B(tài)為饑餓

• 第3格為黑色，蟲(chóng)子饑餓，吃掉食物格子變白，蟲(chóng)子新?tīng)顟B(tài)為吃飽

• 第3格為白色，蟲(chóng)子吃飽，蟲(chóng)子前移一格，到達(dá)第4格，蟲(chóng)子新?tīng)顟B(tài)為饑餓

• 第4格為白色，蟲(chóng)子饑餓，等待食物長(zhǎng)出來(lái)涂黑，蟲(chóng)子新?tīng)顟B(tài)為吃飽

• 第4格為黑色，蟲(chóng)子吃飽，蟲(chóng)子后退一格，到達(dá)第3格，蟲(chóng)子新?tīng)顟B(tài)為饑餓

• 這時(shí)，第3格已經(jīng)長(zhǎng)出來(lái)食物，是黑色，因此流程和第5步的情況一樣了

情況二，小蟲(chóng)的行為比情況以復(fù)雜了一些，但小蟲(chóng)最后仍然會(huì)落入無(wú)限循環(huán)當(dāng)中。

到此，如果你已經(jīng)徹底搞懂了二維蟲(chóng)子是怎么移動(dòng)的，那么你已經(jīng)明白了圖靈機(jī)的工作原理了！因?yàn)閺谋举|(zhì)上講，最后的小蟲(chóng)模型就是一個(gè)圖靈機(jī)！

3如何理解圖靈機(jī)

剛才用二維蟲(chóng)子說(shuō)明了圖靈機(jī)的工作原理，相信你的第一個(gè)反映就是，這樣的模型太簡(jiǎn)單了！

他根本說(shuō)明不了現(xiàn)實(shí)世界中的任何問(wèn)題！下面，我就要試圖說(shuō)服你，圖靈機(jī)這個(gè)模型是偉大的！

其實(shí)蟲(chóng)子的所有決策和行為都可以抽象成一個(gè)圖靈機(jī)模型。

為什么可以做這種抽象呢？

其實(shí)可以把二維蟲(chóng)子的模型進(jìn)行更多擴(kuò)展，以和現(xiàn)實(shí)世界基本或完全一致。因?yàn)槎S蟲(chóng)子模型是以一切都簡(jiǎn)化的前提開(kāi)始的，所以它的確是太太簡(jiǎn)單了。

然而，我們可以把二維蟲(chóng)子的輸入集合、輸出行動(dòng)集合、內(nèi)部狀態(tài)集合進(jìn)行擴(kuò)大，這個(gè)模型就一下子實(shí)用多了。

• 二維蟲(chóng)子完全可以處于一個(gè)三維的空間中而不是簡(jiǎn)簡(jiǎn)單單的紙帶。

• 二維蟲(chóng)子的視力很好，它一下子能讀到方圓500米的信息。

• 二維蟲(chóng)子也可以擁有其他的感覺(jué)器官，比如嗅覺(jué)、聽(tīng)覺(jué)等等，而這些改變都僅僅是擴(kuò)大了輸入集合的維數(shù)和范圍，并沒(méi)有其他更本質(zhì)的改變。

• 二維蟲(chóng)子可能的輸出集合也是異常的豐富，它不僅僅能移動(dòng)自己，還可以盡情的改造它所在的自然界。

• 進(jìn)一步的，二維蟲(chóng)子的內(nèi)部狀態(tài)可能非常的多，而且控制它行為的程序可能異常復(fù)雜

那么二維蟲(chóng)子會(huì)有什么本事呢？這就很難說(shuō)了，因?yàn)殡S著小蟲(chóng)內(nèi)部的狀態(tài)數(shù)的增加，隨著它所處環(huán)境的復(fù)雜度的增加，我們正在逐漸失去對(duì)二維蟲(chóng)子行為的預(yù)測(cè)能力。

但是所有這些改變?nèi)匀粵](méi)有逃出圖靈機(jī)的模型：

"輸入集合、輸出集合、內(nèi)部狀態(tài)、固定的程序指令！"

就是這四樣?xùn)|西抓住了二維蟲(chóng)子信息處理的根本。

4什么是圖靈完備

維基百科解釋?zhuān)?/strong>

可圖靈指在可計(jì)算性理論中，編程語(yǔ)言或任意其他的邏輯系統(tǒng)如具有等用于通用圖靈機(jī)的計(jì)算能力。換言之，此系統(tǒng)可與通用圖靈機(jī)互相模擬。

上面的解釋比較抽象，通過(guò)上面的例子理解了什么是圖靈機(jī)，圖靈完備其實(shí)就很很簡(jiǎn)單理解了。

簡(jiǎn)單來(lái)說(shuō)，能夠抽象成圖靈機(jī)的系統(tǒng)或編程語(yǔ)言就是圖靈完備的；一切可計(jì)算的問(wèn)題圖靈機(jī)都能計(jì)算，因此滿(mǎn)足這樣要求的邏輯系統(tǒng)、裝置或者編程語(yǔ)言就叫圖靈完備的。

因此可見(jiàn)，二維蟲(chóng)子是圖靈完備的。

Bitcoin的腳本由于沒(méi)有條件分支，循環(huán)等控制指令，回到上面的蟲(chóng)子的例子，蟲(chóng)子就不能根據(jù)當(dāng)前狀態(tài)，判斷選擇移動(dòng)還是吃食物等一系列的動(dòng)作，因此不滿(mǎn)足圖靈機(jī)的模型，不是圖靈完備的。

5人也是圖靈機(jī)？

我們?nèi)四懿荒芤脖贿@樣的抽象呢？顯然是可以的。

其實(shí)我們每一個(gè)會(huì)決策、會(huì)思考的人就可以被抽象的看成一個(gè)圖靈機(jī)，也就是笑來(lái)老師一直說(shuō)：每個(gè)人都有自己的操作系統(tǒng)，因?yàn)橛性J(rèn)知能力，還可以自己升級(jí)操作系統(tǒng)。

輸入狀態(tài)集合就是你所處的環(huán)境中能夠看到、聽(tīng)到、聞到、感覺(jué)到的所有一起，可能的輸出集合就是你的每一言每一行，以及你能夠表達(dá)出來(lái)的所有表情動(dòng)作。內(nèi)部狀態(tài)集合則要復(fù)雜得多。因?yàn)槲覀兛梢园讶我庖粋€(gè)神經(jīng)細(xì)胞的狀態(tài)組合看作是一個(gè)內(nèi)部狀態(tài)，那么所有可能的神經(jīng)細(xì)胞的狀態(tài)組合將是天文數(shù)字！這就是人類(lèi)的記憶。只要圖靈機(jī)具有了內(nèi)部狀態(tài)，它就相應(yīng)的具有了記憶。

這樣理解的話(huà)，還有兩個(gè)問(wèn)題：

• 圖靈機(jī)的程序指令是固定的。但是人類(lèi)有學(xué)習(xí)能力，也就是說(shuō)人的大腦會(huì)進(jìn)化，操作系統(tǒng)會(huì)升級(jí)，所以大腦的實(shí)際程序規(guī)則是不固定，似乎圖靈機(jī)模型包含不了。

• 人類(lèi)的很多現(xiàn)象似乎都能被圖靈機(jī)包括：情緒、情感等。

到此，相信大家對(duì)“區(qū)塊鏈的圖靈機(jī)和圖靈完備是什么”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢(xún)，關(guān)注我們，繼續(xù)學(xué)習(xí)！