[迷你学文化] 用生命游戏证明迷你世界GUI功能图灵完备 (可视化可拖拽式编辑器) 第一节

2022-12-13 18:07 作者:伊洛畿戎 0人读过 | 我要投稿

1.背景铺垫

【注意】本大节主要使用改自百度百科的自然语言，而非严格数理定义；为了控制篇幅，仅做了快速简介，并非合格的主题科普。若已了解相关内容，建议跳过对应小节；若对其中的主题感兴趣，请自行搜索更严谨的科普。

1.1.Conway生命游戏

康威生命游戏(Conway's Game of Life)是由英裔数学家约翰・何顿・康威(John Horton Conway)在1970年发明的一套在正方网格上自动运行的游戏规则，是首个被发明的元胞自动机。

本游戏使用B3/S23规则：B3中的B是Birth(诞生)的缩写，意为“当前细胞为死亡状态时，当周围有3个存活细胞时，则迭代后该细胞变成存活状态(模拟繁殖)；若原先为生，则保持不变。”；S23中的S是Survive(存续)的缩写，意为“当前细胞为存活状态时，当周围的邻居细胞低于2个存活时，该细胞变成死亡状态(模拟生命数量稀少)；当周围有2或3个存活细胞时，该细胞保持原样；当周围有3个以上的存活细胞时，该细胞变成死亡状态(模拟生命数量过多)。”

本规则考虑的邻域是一个细胞的周围 8 格，称为 Moore 邻域，如下图：

可以把最初的细胞结构定义为种子，当所有种子细胞按以上规则处理后，可以得到第1代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。

以下动图中，黑色表示活细胞，白色表示死细胞，展现了一个循环移动演化的飞船结构实例：

1.2.(子)系统的功能

系统是一个可以独立存在的完整实体，由一组完成特定任务的功能组成。

功能是使用角度下的定义，主要指特定场景下的输入及其输出，通常来说，一个系统会有多个功能。

子系统顾名思义，它也是一个系统，也就是说仍然是完整的实体。系统和子系统的概念是相对的，当作为另一个系统的一部分时，系统就成为一个子系统。

子系统完全封装自己的内容，只通过自己的接口提供行为，隐藏了实施的所有细节。

可以用子系统表示系统所使用的产品，例如：

通信软件（中间件）、数据库访问支持（RDBMS 映射支持）和应用程序专用产品等。

如《迷你世界》作为程序中的类引擎沙盒游戏，在各操作系统中也可算子系统，包含生存冒险、沙盒创造、地图开发、生态社区等功能。

1.3.Turing计算机

图灵机(Turing machine)，又称图灵计算机，是英国数学家艾伦・麦席森・图灵(Alan Mathison Turing)于1936年提出的一种抽象的计算模型，即将人们使用纸笔进行数学运算的过程进行抽象，由一个虚拟的机器替代人类进行数学运算。

图灵机包含一条无限长的纸带(意味着无限存储)，分成一个个小方格，每个方格上有一个单位信息。图灵机用一个机器头在纸带上移来移去，其有一组内部状态和固定的程序集合。每单位时间，机器头都要从当前纸带上读入一个方格信息，然后结合自己的内部状态查找程序表，根据程序输出信息到纸带方格上，并转换自己的内部状态，再进行移动。

1.4.通用图灵机与可计算性理论

对于任意一个图灵机，因其描述所需信息有限，因此我们总可以用某种方式将其编码为字符串。由此延伸，可以构造出一个特殊的图灵机，它接受任意一个图灵机的编码，然后模拟其运作（甚至可以作为自模拟虚拟机，模拟自己的运作），这样的图灵机称为通用图灵机(universal Turing machine)。

现代电子计算机其实就是这样一种通用图灵机(的有限近似)，它能接受一段描述其他图灵机(的有限近似)的程序，并运行程序以实现该程序所描述的算法。但要注意这些都只是有限近似，因为现实中的计算机的存储都有限，所以无法跨越有限状态机的界限。

图灵机有很多变种，但可以证明这些变种的计算能力都等价，即它们都识别乔姆斯基层次结构(Chomsky hierarchy)中的0-型语言(递归可枚举语言)，处理能行可计算函数(部分递归函数)。

1.5.Turing完备及其证明方法

根据图灵等价(Turing equivalence)，任意两台通用图灵机都能互相模拟。由此可证明，若任意逻辑系统能模拟通用图灵机，则该系统的可计算性等价于图灵机，称为图灵完备(Turing completeness)。

所以说，证明一个功能系统图灵完备的简单方法，可以是用它模拟一个其它的图灵完备系统。有很多简易的选择，比如Brainfuck(BF)和Smallfuck(SF)等简单的语言。一个可视化效果比较好的例子是：通过模拟回文识别器(palindrome recognizer)，卡内基梅隆大学的Tom Wildenhain证明了PPT的动画功能图灵完备。

B站转载视频之一的链接

而可视化效果更直观的选择其实还有生命游戏，因为生命游戏等相当多元胞自动机也陆续被证明了图灵完备。其实有相当多系统和功能被意外发现并被证明是图灵完备的，比如C++的模板系统、Java的泛型系统和HTML5+CSS3体系等。还有很多被附加了功能，以达到图灵完备，比如微软办公套装(Microsoft Office)中内置的VBA宏，常见的有Word、Excel和上面提过的PowerPoint。也就是说，其实一个系统中有多个相对独立的、各自图灵完备的子系统，这种情况并不罕见。

1.6.显示屏上的GUI

图形用户界面（Graphical User Interface，简称 GUI，又称图形用户接口）是一种人与计算机通信的界面显示格式，允许用户使用鼠标和触屏等人机交互方式，操纵显示屏上的图标或菜单选项，以执行选择命令、调用文件、启动程序等日常任务。在电脑和手机等不同终端上，会有不同的需求特点和表现形式。

与通过键盘输入文本或字符命令来完成例行任务的字符界面相比，图形用户界面有许多优点。