什么是圖靈完備性（Turingcomplete）

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