題記：看資料時(shí)經(jīng)承虢蹋看到圖靈完備這四個(gè)字，但完全不知道什么意思斩芭，所以整理了關(guān)于圖靈完備的資料轻腺。
1.圖靈
艾倫·麥席森·圖靈（Alan Mathison Turing，1912年6月23日－1954年6月7日）划乖，英國(guó)數(shù)學(xué)家贬养、邏輯學(xué)家，被稱為計(jì)算機(jī)科學(xué)之父琴庵，人工智能之父误算。
2.圖靈機(jī)
圖靈機(jī)，又稱圖靈計(jì)算迷殿、圖靈計(jì)算機(jī)儿礼，是由數(shù)學(xué)家艾倫·麥席森·圖靈（1912～1954）提出的一種抽象計(jì)算模型，即將人們使用紙筆進(jìn)行數(shù)學(xué)運(yùn)算的過(guò)程進(jìn)行抽象庆寺，由一個(gè)虛擬的機(jī)器替代人們進(jìn)行數(shù)學(xué)運(yùn)算蚊夫。它有一條無(wú)限長(zhǎng)的紙帶，紙帶分成了一個(gè)一個(gè)的小方格懦尝，每個(gè)方格有不同的顏色知纷。有一個(gè)機(jī)器頭在紙帶上移來(lái)移去。機(jī)器頭有一組內(nèi)部狀態(tài)陵霉，還有一些固定的程序琅轧。在每個(gè)時(shí)刻，機(jī)器頭都要從當(dāng)前紙帶上讀入一個(gè)方格信息踊挠，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表乍桂，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，然后進(jìn)行移動(dòng)模蜡。
以上只是圖靈機(jī)模型的內(nèi)容，而非具體的實(shí)現(xiàn)扁凛。
圖靈機(jī)可以解決什么問(wèn)題
假設(shè)上述模型里所說(shuō)的功能都能被以某種形式物理實(shí)現(xiàn)忍疾，那么任意可計(jì)算問(wèn)題都可以被解決。
計(jì)算問(wèn)題的一些舉例：
- 給定一個(gè)正整數(shù)n谨朝，判斷它是否是質(zhì)數(shù)
- 給定一個(gè)01序列卤妒，把他們按位取反
- 給定一個(gè)字符串，判斷某個(gè)字符是否存在字币，及查找存在位置
- 給定一個(gè)邏輯蘊(yùn)含的命題则披，求它的逆否命題
非計(jì)算問(wèn)題的例子：
- 今晚吃什么
- 為什么太陽(yáng)從東邊升起
3.什么是圖靈完備？
在可計(jì)算性理論里洗出，如果一系列操作數(shù)據(jù)的規(guī)則（如指令集士复、編程語(yǔ)言、細(xì)胞自動(dòng)機(jī)）按照一定的順序可以計(jì)算出結(jié)果翩活，被稱為圖靈完備（turing complete）阱洪。
一個(gè)有圖靈完備指令集的設(shè)備被定義為通用計(jì)算機(jī)。如果是圖靈完備的菠镇，它（計(jì)算機(jī)設(shè)備）有能力執(zhí)行條件跳轉(zhuǎn)（if冗荸、while、goto語(yǔ)句）以及改變內(nèi)存數(shù)據(jù)利耍。 如果某個(gè)東西展現(xiàn)出了圖靈完備蚌本，它就有能力表現(xiàn)出可以模擬原始計(jì)算機(jī)，而即使最簡(jiǎn)單的計(jì)算機(jī)也能模擬出最復(fù)雜的計(jì)算機(jī)隘梨。所有的通用編程語(yǔ)言和現(xiàn)代計(jì)算機(jī)的指令集都是圖靈完備的（C++ template就是圖靈完備的）程癌，都能解決內(nèi)存有限的問(wèn)題。圖靈完備的機(jī)器都被定義有無(wú)限內(nèi)存出嘹，但是機(jī)器指令集卻通常定義為只工作在特定的席楚、有限數(shù)量的RAM上。
圖靈完備的語(yǔ)言税稼，有循環(huán)執(zhí)行語(yǔ)句烦秩，判斷分支語(yǔ)句等。理論上能解決任何算法郎仆。但有可能進(jìn)入死循環(huán)而程序崩潰只祠。
圖靈不完備也不是沒(méi)有意義，有些場(chǎng)景我們需要限制語(yǔ)言本身扰肌。如限制循環(huán)和遞歸, 可以保證該語(yǔ)言能寫(xiě)的程序一定是終止的抛寝。
比特幣的腳本系統(tǒng)是圖靈不完備的，以太坊的智能合約系統(tǒng)是圖靈完備的。各有優(yōu)缺點(diǎn)盗舰，圖靈不完備會(huì)更安全些晶府，圖靈完備會(huì)更智能些。
