1.背景鋪墊

【注意】本大節(jié)主要使用改自百度百科的自然語言，而非嚴格數(shù)理定義；為了控制篇幅，僅做了快速簡介，并非合格的主題科普。若已了解相關(guān)內(nèi)容，建議跳過對應小節(jié)；若對其中的主題感興趣，請自行搜索更嚴謹?shù)目破铡?/span>

1.1.Conway生命游戲

康威生命游戲(Conway's Game of Life)是由英裔數(shù)學家約翰?何頓?康威(John Horton Conway)在1970年發(fā)明的一套在正方網(wǎng)格上自動運行的游戲規(guī)則，是首個被發(fā)明的元胞自動機。

本游戲使用B3/S23規(guī)則：B3中的B是Birth(誕生)的縮寫，意為“當前細胞為死亡狀態(tài)時，當周圍有3個存活細胞時，則迭代后該細胞變成存活狀態(tài)(模擬繁殖)；若原先為生，則保持不變?！?；S23中的S是Survive(存續(xù))的縮寫，意為“當前細胞為存活狀態(tài)時，當周圍的鄰居細胞低于2個存活時，該細胞變成死亡狀態(tài)(模擬生命數(shù)量稀少)；當周圍有2或3個存活細胞時，該細胞保持原樣；當周圍有3個以上的存活細胞時，該細胞變成死亡狀態(tài)(模擬生命數(shù)量過多)。”

本規(guī)則考慮的鄰域是一個細胞的周圍 8 格，稱為 Moore 鄰域，如下圖：

可以把最初的細胞結(jié)構(gòu)定義為種子，當所有種子細胞按以上規(guī)則處理后，可以得到第1代細胞圖。按規(guī)則繼續(xù)處理當前的細胞圖，可以得到下一代的細胞圖，周而復始。

以下動圖中，黑色表示活細胞，白色表示死細胞，展現(xiàn)了一個循環(huán)移動演化的飛船結(jié)構(gòu)實例：

1.2.(子)系統(tǒng)的功能

系統(tǒng)是一個可以獨立存在的完整實體，由一組完成特定任務(wù)的功能組成。

功能是使用角度下的定義，主要指特定場景下的輸入及其輸出，通常來說，一個系統(tǒng)會有多個功能。

子系統(tǒng)顧名思義，它也是一個系統(tǒng)，也就是說仍然是完整的實體。系統(tǒng)和子系統(tǒng)的概念是相對的，當作為另一個系統(tǒng)的一部分時，系統(tǒng)就成為一個子系統(tǒng)。

子系統(tǒng)完全封裝自己的內(nèi)容，只通過自己的接口提供行為，隱藏了實施的所有細節(jié)。

可以用子系統(tǒng)表示系統(tǒng)所使用的產(chǎn)品，例如：

通信軟件（中間件）、數(shù)據(jù)庫訪問支持（RDBMS 映射支持）和應用程序?qū)Ｓ卯a(chǎn)品等。

如《迷你世界》作為程序中的類引擎沙盒游戲，在各操作系統(tǒng)中也可算子系統(tǒng)，包含生存冒險、沙盒創(chuàng)造、地圖開發(fā)、生態(tài)社區(qū)等功能。

1.3.Turing計算機

圖靈機(Turing machine)，又稱圖靈計算機，是英國數(shù)學家艾倫?麥席森?圖靈(Alan Mathison Turing)于1936年提出的一種抽象的計算模型，即將人們使用紙筆進行數(shù)學運算的過程進行抽象，由一個虛擬的機器替代人類進行數(shù)學運算。

圖靈機包含一條無限長的紙帶(意味著無限存儲)，分成一個個小方格，每個方格上有一個單位信息。圖靈機用一個機器頭在紙帶上移來移去，其有一組內(nèi)部狀態(tài)和固定的程序集合。每單位時間，機器頭都要從當前紙帶上讀入一個方格信息，然后結(jié)合自己的內(nèi)部狀態(tài)查找程序表，根據(jù)程序輸出信息到紙帶方格上，并轉(zhuǎn)換自己的內(nèi)部狀態(tài)，再進行移動。

1.4.通用圖靈機與可計算性理論

對于任意一個圖靈機，因其描述所需信息有限，因此我們總可以用某種方式將其編碼為字符串。由此延伸，可以構(gòu)造出一個特殊的圖靈機，它接受任意一個圖靈機的編碼 ，然后模擬其運作（甚至可以作為自模擬虛擬機，模擬自己的運作），這樣的圖靈機稱為通用圖靈機(universal Turing machine)。

現(xiàn)代電子計算機其實就是這樣一種通用圖靈機(的有限近似)，它能接受一段描述其他圖靈機(的有限近似)的程序，并運行程序以實現(xiàn)該程序所描述的算法。但要注意這些都只是有限近似，因為現(xiàn)實中的計算機的存儲都有限，所以無法跨越有限狀態(tài)機的界限。

圖靈機有很多變種，但可以證明這些變種的計算能力都等價，即它們都識別喬姆斯基層次結(jié)構(gòu)(Chomsky hierarchy)中的0-型語言(遞歸可枚舉語言)，處理能行可計算函數(shù)(部分遞歸函數(shù))。

1.5.Turing完備及其證明方法

根據(jù)圖靈等價(Turing equivalence)，任意兩臺通用圖靈機都能互相模擬。由此可證明，若任意邏輯系統(tǒng)能模擬通用圖靈機，則該系統(tǒng)的可計算性等價于圖靈機，稱為圖靈完備(Turing completeness)。

所以說，證明一個功能系統(tǒng)圖靈完備的簡單方法，可以是用它模擬一個其它的圖靈完備系統(tǒng)。有很多簡易的選擇，比如Brainfuck(BF)和Smallfuck(SF)等簡單的語言。一個可視化效果比較好的例子是：通過模擬回文識別器(palindrome recognizer)，卡內(nèi)基梅隆大學的Tom Wildenhain證明了PPT的動畫功能圖靈完備。

B站轉(zhuǎn)載視頻之一的鏈接

而可視化效果更直觀的選擇其實還有生命游戲，因為生命游戲等相當多元胞自動機也陸續(xù)被證明了圖靈完備。其實有相當多系統(tǒng)和功能被意外發(fā)現(xiàn)并被證明是圖靈完備的，比如C++的模板系統(tǒng)、Java的泛型系統(tǒng)和HTML5+CSS3體系等。還有很多被附加了功能，以達到圖靈完備，比如微軟辦公套裝(Microsoft Office)中內(nèi)置的VBA宏，常見的有Word、Excel和上面提過的PowerPoint。也就是說，其實一個系統(tǒng)中有多個相對獨立的、各自圖靈完備的子系統(tǒng)，這種情況并不罕見。

1.6.顯示屏上的GUI

圖形用戶界面（Graphical User Interface，簡稱 GUI，又稱圖形用戶接口）是一種人與計算機通信的界面顯示格式，允許用戶使用鼠標和觸屏等人機交互方式，操縱顯示屏上的圖標或菜單選項，以執(zhí)行選擇命令、調(diào)用文件、啟動程序等日常任務(wù)。在電腦和手機等不同終端上，會有不同的需求特點和表現(xiàn)形式。

與通過鍵盤輸入文本或字符命令來完成例行任務(wù)的字符界面相比，圖形用戶界面有許多優(yōu)點。

GUI由視窗、文本框、按鈕、下拉式菜單等用戶界面控件構(gòu)成，對該系統(tǒng)內(nèi)任意APP都是標準化的，即相同的操作總是以同樣的方式來完成。在圖形用戶界面，用戶看到和操作的都是圖形對象，應用的是計算機圖形學的技術(shù)。

而《迷你世界》的UI庫功能就像JAVA和WinForm等一樣，內(nèi)置了可拖曳式的GUI編輯器，能讓創(chuàng)作者在游戲里自主創(chuàng)造自己的跨終端UI圖形。

下一節(jié)：