~ read.
[.計算機科學]圖靈完備性

[.計算機科學]圖靈完備性

最近又和同行論及一個老話題,廣義語境下的html5是否能算編程語言,這不得不又談到了圖靈完備性的話題,看了下網路上與之相關的詳細論述甚少,故總結一篇,以備查詢...

什麼是圖靈機

圖靈機(Turing Machine)是圖靈在1936年發表的 "On Computable Numbers, with an Application to the Entscheidungsproblem"(《論可計算數及其在判定性問題上的應用》)中提出的數學模型。

\[M = (Q, \sum , \Gamma , \delta , q_{0}, q_{accept}, q_{reject})\]

既然是數學模型,它就並非一個實體概念,而是架空的一個想法。在文章中圖靈描述了它是什麼,並且證明了,只要圖靈機可以被實現,就可以用來解決任何的可計算問題。

圖靈機的結構包括以下幾個部分:

  1. 一條無限長的紙帶(tape),紙帶被分成一個個相鄰的格子(square),每個格子都可以寫上至多一個字符(symbol)。

  2. 一個字符表(alphabet),即字符的集合,它包含紙帶上可能出現的所有字符。其中包含一個特殊的空白字符(blank),意思是此格子沒有任何字符。

  3. 一個讀寫頭(head),可理解為指向其中一個格子的指針。它可以讀取/擦除/寫入當前格子的內容,此外也可以每次向左/右移動一個格子。

  4. 一個狀態寄存器(state register),它追蹤著每一步運算過程中,整個機器所處的狀態(運行/終止)。當這個狀態從運行變為終止,則運算結束,機器停機並交回控制權。如果你瞭解有限狀態機,它便對應著有限狀態機里的狀態。

  5. 一個有限的指令集(instructions table),它記錄著讀寫頭在特定情況下應該執行的行為。可以想象讀寫頭隨身有一本操作指南,裡面記錄著很多條類似於「當你身處編號53的格子並看到其內容為0時,擦除,改寫為1,並向右移一格。此外,令下一狀態為運行。」這樣的命令。其實某種意義上,這個指令集就對應著程序員所寫下的程序了。

在計算開始前,紙帶可以是完全空白,也可以在某些格子里預先就有寫上部分字符作為輸入。運算開始時,讀寫頭從某一位置開始,嚴格按照此刻的配置(configuration),即:

  • 當前所處位置
  • 當前格子內容

來一步步的對照著指令集去進行操作,直到狀態變為停止,運算結束。而後紙帶上留下的信息,即字符的序列(比如類似...011001...)便作為輸出,由人來解碼為自然語言。

要重申一下,以上只是圖靈機模型的內容,而非具體的實現。所謂的紙帶和讀寫頭都只是圖靈提出的抽象概念。為便於理解打一個比方。算盤雖然不是圖靈機(因為它沒有無限長的紙帶,即無限的存儲空間),但它的行為與圖靈機一致。每一串算珠都是紙帶上的一格,一串算珠上展示的數字便記錄著當前格中的字符(可以是空白,可以是12345)。人類的手即是讀寫頭,可以更改每串算珠的狀態。算盤的運行遵循人腦中的算法,當算法結束,算盤停機。

圖靈機可以解決什麼問題

在文章中,圖靈所做的事是證明了,假設上述模型里所說的功能都能被以某種形式物理實現,那麼任意可計算問題都可以被解決。這裡所說的可計算問題,涉及到計算理論(Computation Theory)的概念。這個領域的概念很繁雜,先簡單梳理一下。

在計算機領域,或者說自動機領域,我們研究的一切問題都是計算問題(Computational Problem)。它泛指一切與計算相關的問題。

A computational problem is a mathematical object representing a collection of questions that computers might be able to solve.

計算問題的一些舉例:

  1. 給定一個正整數n,判斷它是否是質數;
  2. 給定一個01序列,把它們按位取反;
  3. 給定一個字符串,判斷某個字符是否存在,及查找存在位置;
  4. 給定一個邏輯蘊含的命題,求它的逆否命題;

非計算問題的例子:

  • 今晚吃什麼
  • 為什麼太陽從東邊升起

計算問題有的可以解決,有的不可解決。這就引出了計算問題的可計算性(Computability)。它可以被理解為「是否存在一個算法,能解決在任何輸入下的此計算問題」。如上面的問題[1],我們當然可以找到一個算法來解決判斷任意正整數n是否為質數的問題(比如從2遍歷到n-1,看n是否可以整除它)。所以,問題[1]就是可計算的。

也有一些不可計算的計算問題,比如著名的停機問題(Halting Problem)。它的表述是這樣的:給定一段程序的描述和該程序的一個有效輸入,運行此程序,那麼程序最終是會終止,還是會死循環下去?

Halting Problem: given the description of an arbitrary program and a finite input, decide whether the program finishes running or will run forever.

這個問題很繞人,有點像那個著名的理髮師悖論,但它確實是一個計算問題。更具體的,它是一個不可判定問題(Undecidable Problem)。即不存在一個通用算法,可以在任意輸入下解決此問題。圖靈在文章里很優雅的用反證法推翻了假設「假設有這麼一個算法可以解決任何停機問題」,從而證明瞭這樣的算法並不存在。

回到這一節的主題。簡而言之,對於一個問題,對於任意輸入,只要人類可以保證算出結果(不管花多少時間),那麼圖靈機就可以保證算出結果(不管花多少時間)。

圖靈完備性

圖靈完備性(Turing Completeness)是針對一套數據操作規則而言的概念。數據操作規則可以是一門編程語言,也可以是計算機里具體實現了的指令集。當這套規則可以實現圖靈機模型里的全部功能時,就稱它具有圖靈完備性。直白一點說,圖靈完備性就是我給你一工具箱的東西,包括無限內存、if...{}else{} 控制流、while{}循環 ... 那麼你現在圖靈完備了嗎?

概念本身倒是非常直觀,但整件事似乎還是讓人雲里霧裡。我曾經一直不懂的就是為什麼圖靈給出的那個命題是正確的。換句話說,憑什麼有了紙帶以及其他的那一套東西,就可以自信解決任意可計算問題呢?儘管我不能通讀他的那篇論文里的證明,但是通過一門叫做Brainfuck的編程語言,還是可以獲得一些直覺。

直觀理解圖靈完備 —— Brainfuck語言

如今主流的編程語言(C++,Java,Python等等)都是圖靈完備的語言。關於語言優劣之爭也只是在其封裝、優化等方面,以及因為這些區別而產生的「不同語言適用於不同情況」的爭執。如果我們回到最底層,就會發現它們可以實現的功能其實完全一樣,並且本質上就是一個圖靈機。

在1993年,Urban Müller 發明瞭 Brainfuck 語言。這門語言可以說是編程語言界的 helloworld 了——它一共只含有 8 個有效字符,每個有效字符就是一條指令。語言雖然極致輕量,它卻是一門圖靈完備的編程語言。如果能理解它的工作原理,那麼對於理解圖靈機是有很大幫助的。

Brainfuck is fully Turing-complete.

先貼上一段 BF 的代碼,體驗一下它的畫風:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++
.------.--------.>>+.>++.

這個程序編譯運行後,控制台打印 "Hello World!"。

BF 的工作機制與圖靈機高度一致。首先它存儲數據的方式是一個不限長的一維整數數組,裡面的數值全部初始化為0。此外,有一數據指針,每一時刻都指向數組的某一任意元素。指針可以向左/右移動,也可以讀取/修改當前值。

語言里的 8 個有效字符分別是:

  • > 指針向右移動一格
  • < 指針向左移動一格
  • + 使指針當前格數值加一
  • - 使指針當前格數值減一
  • . 把當前格數值按 ASCII 表輸出到終端
  • , 從終端接受一 byte 的數據,存儲其 ASCII 數值到當前格
  • [ 當指針當前值為 0 時,程序跳轉至與之對應的]之後;否則程序正常執行
  • ] 程序跳轉回與之對應的[

有了這些工具,我們可以很快做出一個計算乘法的程序。因為 ASCII 表中 'A' 對應的值為 65,可以使用 5 * 13 算出 65 並輸出得到字符 'A'。

+++++

[
>+++++++++++++
<-  
]

>.

把指針初始處的格子命名為 cell 0,cell 0 右邊的那個格子命名為 cell 1。那麼第一句將其遞增 5 次變為 5。然後,循環執行「右移指針,遞增 13 次, 左移指針,遞減 1 次」。當 cell 0 的值最終被遞減為 0 的時候,循環結束。此時 cell 1 的值執行了 5 次「遞增 13 次」的操作,即 65。指針右移至 cell 1,輸出此格子,則在終端會看到 'A'。

最初的討論

回到那個最初的討論。

根據上面對圖靈完備性的論述,用它來檢驗html,你會發現,他不像Java,C++,Python等語言,具有很強的邏輯性和流程控制功能。他不能按照人類的設計,對一件工作進行重復的循環,直至得到讓人類滿意的答案。這一點最重要,其他語言都可以輕鬆做到。

所以,html並不是一門編程語言!

———————————
© 2020. All rights reserved. Setup on Dedicate Server in Europe . Built by Mille Yin.