什么是圖靈完備性（Turingcomplete）？這是?篇旨在幫助理解圖靈機及相關概念是什么，??證明其正確性的回答，它包含以下內容：1.什么是圖靈機2.圖靈機可以解決什么問題3.什么是圖靈完備4.直觀理解圖靈完備——Brainfuck語?1.什么是圖靈機圖靈機（TuringMachine）是圖靈在1936年發表的"OnComputableNumbers,withanApplicationtotheEntscheidungsproblem"（《論可計算數及其在判定性問題上的應?》）中提出的數學模型。既然是數學模型，它就并??個實體概念，?是架空的?個想法。在?章中圖靈描述了它是什么，并且證明了，只要圖靈機可以被實現，就可以?來解決任何可計算問題。圖靈機的結構包括以下?個部分：1.?條?限長的紙帶（tape），紙帶被分成?個個相鄰的格?（square），每個格?都可以寫上?多?個字符（symbol）。2.?個字符表（alphabet），即字符的集合，它包含紙帶上可能出現的所有字符。其中包含?個特殊的空?字符（blank），意思是此格?沒有任何字符。3.?個讀寫頭（head），可理解為指向其中?個格?的指針。它可以讀取/擦除/寫?當前格?的內容，此外也可以每次向左/右移動?個格?。4.?個狀態寄存器（stateregister），它追蹤著每?步運算過程中，整個機器所處的狀態（運?/終?）。當這個狀態從運?變為終?，則運算結束，機器停機并交回控制權。如果你了解有限狀態機，它便對應著有限狀態機?的狀態。5.?個有限的指令集（instructionstable），它記錄著讀寫頭在特定情況下應該執?的?為。可以想象讀寫頭隨?有?本操作指南，??記錄著很多條類似于“當你?處編號53的格?并看到其內容為0時，擦除，改寫為1，并向右移?格。此外，令下?狀態為運?。”這樣的命令。其實某種意義上，這個指令集就對應著程序員所寫下的程序了。圖靈機結構在計算開始前，紙帶可以是完全空?，也可以在某些格??預先就有寫上部分字符作為輸?。運算開始時，讀寫頭從某?位置開始，嚴格按照此刻的配置（configuration），即：當前所處位置當前格?內容來?步步的對照著指令集去進?操作，直到狀態變為停?，運算結束。?后紙帶上留下的信息，即字符的序列（?如類似“...011001...”）便作為輸出，由?來解碼為?然語?。要重申?下，以上只是圖靈機模型的內容，??具體的實現。所謂的紙帶和讀寫頭都只是圖靈提出的抽象概念。為便于理解打?個??。算盤雖然不是圖靈機（因為它沒有?限長的紙帶，即?限的存儲空間），但它的?為與圖靈機?致。每?串算珠都是紙帶上的?格，?串算珠上展?的數字便記錄著當前格中的字符（可以是空?，可以是12345）。?類的?即是讀寫頭，可以更改每串算珠的狀態。算盤的運?遵循?腦中的算法，當算法結束，算盤停機。2.圖靈機可以解決什么問題在?章中，圖靈所做的事是證明了，假設上述模型?所說的功能都能被以某種形式物理實現，那么任意可計算問題都可以被解決。這?所說的可計算問題，涉及到計算理論（ComputationTheory）的概念。這個領域的概念很繁雜，先簡單梳理?下。在計算機領域，或者說?動機領域，我們研究的?切問題都是計算問題（ComputationalProblem）。它泛指?切與計算相關的問題。Acomputationalproblemisamathematicalobjectrepresentingacollectionofquestionsthatcomputersmightbeabletosolve.計算問題的?些舉例：1.給定?個正整數n，判斷它是否是質數2.給定?個01序列，把它們按位取反3.給定?個字符串，判斷某個字符是否存在，及查找存在位置4.給定?個邏輯蘊含的命題，求它的逆否命題?計算問題的例?：今晚吃什么為什么太陽從東邊升起計算問題有的可以解決，有的不可解決。這就引出了計算問題的可計算性（Computability）。它可以被理解為“是否存在?個算法，能解決在任何輸?下的此計算問題”。如上?的問題1，我們當然可以找到?個算法來解決判斷任意正整數n是否為質數的問題（?如從2遍歷到n-1，看n是否可以整除它）。所以，問題1就是可計算的。也有?些不可計算的計算問題，?如著名的停機問題（HaltingProblem）。它的表述是這樣的：給定?段程序的描述和該程序的?個有效輸?，運?此程序，那么程序最終是會終?，還是會死循環下去？HaltingProblem:giventhedescriptionofanarbitraryprogramandafiniteinput,decidewhethertheprogramfinishesrunningorwillrunforever.這個問題很繞?，有點像那個著名的理發師悖論，但它確實是?個計算問題。更具體的，它是?個不可判定問題（UndecidableProblem）。即不存在?個通?算法，可以在任意輸?下解決此問題。圖靈在?章?很優雅的?反證法推翻了假設“假設有這么?個算法可以解決任何停機問題”，?證明了這樣的算法并不存在。具體證明過程?上的資料?常豐富，我就不再花篇幅了。回到這?節的主題。簡??之，對于?個問題，對于任意輸?，只要?類可以保證算出結果（不管花多少時間），那么圖靈機就可以保證算出結果（不管花多少時間）。3.什么是圖靈完備圖靈完備性（TuringCompleteness）是針對?套數據操作規則??的概念。數據操作規則可以是?門編程語?，也可以是計算實現了的指令集。當這套規則可以實現圖靈機模型?的全部功能時，就稱它具有圖靈完備性。直??點說，圖靈完備性就是我給你??具箱的東西，包括?限內存、if/else控制流、while循環……那么你現在圖靈完備了嗎？概念本?倒是?常直觀，但整件事似乎還是讓?云?霧?。我曾經?直不懂的就是為什么圖靈給出的那個命題是正確的。換句話說，憑什么有了紙帶以及其他的那?套東西，就可以?信解決任意可計算問題呢？盡管我不能通讀他的那篇論??的證明，但是通過?門叫做Brainfuck的編程語?，還是可以獲得?些直覺。4.直觀理解圖靈完備——Brainfuck語?如今主流的編程語?（C++，Java，Python，以及等等等等）都是圖靈完備的語?。關于語?優劣之爭也只是在其封裝、優化等??，以及因為這些區別?產?的“不同語?適?于不同情況”的爭執。如果我們回到最底層，就會發現它們可以實現的功能其實完全?樣，并且本質上就是?個圖靈機。在1993年，UrbanMüller發明了Brainfuck語?。這門語?可以說是編程語?界的helloworld了——它?共只含有8個有效字符，每個有效字符就是?條指令。語?雖然極致輕量，它卻是?門圖靈完備的編程語?。如果能理解它的?作原理，那么對于理解圖靈機是有很?幫助的。BrainfuckisfullyTuring-complete.先貼上?段BF的代碼，體驗?下它的畫風：++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.這個程序編譯運?后，控制臺打印"HelloWorld!"。BF的?作機制與圖靈機?度?致。?先它存儲數據的?式是?個不限長的?維整數數組，??的數值全部初始化為0。此外，有?數據指針，每?時刻都指向數組的某?任意元素。指針可以向左/右移動，也可以讀取/修改當前值。語??的8個有效字符分別是：>指針向右移動?格<指針向左移動?格+使指針當前格數值加?-使指針當前格數值減?.把當前格數值按ASCII表輸出到終端,從終端接受?byte的數據，存儲其ASCII數值到當前格[當指針當前值為0時，程序跳轉?與之對應的]之后；否則程序正常執?]程序跳轉回與之對應的[處有了這些?具，我們可以很快做出?個計算乘法的程序。因為ASCII表中'A'對應的值為65，可以使?5*13算出65并輸出得到字符'A'。+++++[>+++++++++++++<-]>.把指針初始處的格?命名為cell0，cell