題記：看資料時經(jīng)?？吹綀D靈完備這四個字，但完全不知道什么意思，所以整理了關于圖靈完備的資料。
1.圖靈
艾倫·麥席森·圖靈（Alan Mathison Turing，1912年6月23日－1954年6月7日），英國數(shù)學家、邏輯學家，被稱為計算機科學之父，人工智能之父。
2.圖靈機
圖靈機，又稱圖靈計算、圖靈計算機，是由數(shù)學家艾倫·麥席森·圖靈（1912～1954）提出的一種抽象計算模型，即將人們使用紙筆進行數(shù)學運算的過程進行抽象，由一個虛擬的機器替代人們進行數(shù)學運算。它有一條無限長的紙帶，紙帶分成了一個一個的小方格，每個方格有不同的顏色。有一個機器頭在紙帶上移來移去。機器頭有一組內(nèi)部狀態(tài)，還有一些固定的程序。在每個時刻，機器頭都要從當前紙帶上讀入一個方格信息，然后結合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進行移動。
以上只是圖靈機模型的內(nèi)容，而非具體的實現(xiàn)。
圖靈機可以解決什么問題
假設上述模型里所說的功能都能被以某種形式物理實現(xiàn)，那么任意可計算問題都可以被解決。
計算問題的一些舉例：
- 給定一個正整數(shù)n，判斷它是否是質(zhì)數(shù)
- 給定一個01序列，把他們按位取反
- 給定一個字符串，判斷某個字符是否存在，及查找存在位置
- 給定一個邏輯蘊含的命題，求它的逆否命題
非計算問題的例子：
- 今晚吃什么
- 為什么太陽從東邊升起
3.什么是圖靈完備？
在可計算性理論里，如果一系列操作數(shù)據(jù)的規(guī)則（如指令集、編程語言、細胞自動機）按照一定的順序可以計算出結果，被稱為圖靈完備（turing complete）。
一個有圖靈完備指令集的設備被定義為通用計算機。如果是圖靈完備的，它（計算機設備）有能力執(zhí)行條件跳轉(zhuǎn)（if、while、goto語句）以及改變內(nèi)存數(shù)據(jù)。 如果某個東西展現(xiàn)出了圖靈完備，它就有能力表現(xiàn)出可以模擬原始計算機，而即使最簡單的計算機也能模擬出最復雜的計算機。所有的通用編程語言和現(xiàn)代計算機的指令集都是圖靈完備的（C++ template就是圖靈完備的），都能解決內(nèi)存有限的問題。圖靈完備的機器都被定義有無限內(nèi)存，但是機器指令集卻通常定義為只工作在特定的、有限數(shù)量的RAM上。
圖靈完備的語言，有循環(huán)執(zhí)行語句，判斷分支語句等。理論上能解決任何算法。但有可能進入死循環(huán)而程序崩潰。
圖靈不完備也不是沒有意義，有些場景我們需要限制語言本身。如限制循環(huán)和遞歸, 可以保證該語言能寫的程序一定是終止的。
比特幣的腳本系統(tǒng)是圖靈不完備的，以太坊的智能合約系統(tǒng)是圖靈完備的。各有優(yōu)缺點，圖靈不完備會更安全些，圖靈完備會更智能些。
