Turing Complete Turing Complete Guide 157

0. 写此攻略的目的

这篇攻略给没有或很少相关背景知识储备的玩家提供一些过关所需的背景知识。特别是每阶段关卡的目的并利用元件工坊帮助玩家构建过关需要的两大CPU架构（Overture与LEG）。

逛了一圈论坛没有发现简体中文的资料，所以我想写一篇不仅仅提供答案也顺便把游戏背后的一些知识点弄明白的攻略给大多数对计算机科学或数理逻辑感兴趣的非专业读者。废话不多说，开始游戏！

本攻略保持更新。

1. 基础逻辑电路

目标此阶段玩家需要熟悉使用与非门制造各种常见的逻辑门。这些逻辑门将作为底层元件用以构造更复杂的计算机功能，例如运算与存储。

1.1 真值表

真值表是对每个逻辑运算符在不同逻辑变量的可能性下的真值指派表格。

以下是常见逻辑运算符与或非的真值表

否定（非）：对变量的值取反（记为x')

x NOT 1 0 0 1 合取（与）：值为真当且仅当两个变量的值同时为真（记为xy）

x y AND 1 1 1 1 0 0 0 1 0 0 0 0 析取（或）：值为真当且仅当至少一个变量的值为真（记为x+y）

x y OR 1 1 1 1 0 1 0 1 1 0 0 0 若无括号，则规定运算优先级：否定，合取，析取并从左到右计算。例如xy'z+x'等于((x(y'))z)+(x')。

1.2 布尔代数

布尔代数是一种二元运算系统，由逻辑变量、常量0与1、与或非逻辑运算组成并满足以下运算律：

结合律 (xy)z=x(yz) (x+y)+z = x+(y+z) 交换律 xy=yx x+y=y+x 吸收律 xy+x=x (x+y)x=x 分配律 xy+z=(x+z)(y+z) (x+y)z=xz+yz 互补律 xx'=0 x+x'=1 幂等律 xx=x x+x=x 有界律 x1=x x0=0 x+1=1 x+0=x 双重否定律 x''=x 德摩根定律 (xy)'=x'+y' (x+y)'=x'y' 了解这些运算律，我们在游戏的时候就可以通过这些运算律优化我们的电路设计以减少逻辑门的使用与延迟。例如根据分配律，我们可以把逻辑门的使用量从三个减少为两个。

德摩根定律可以让我们在与门、或门、与非门和或非门之间进行转换。相同颜色的电路表示这些电路逻辑等价，左右转换输出值取反，上下转换两个输入值同时取反。

1.3 逻辑电路分析

条件控制任意逻辑电路我们都可以用与门和或门来实践电路条件的精确控制。因为结合律与交换律，多个与门或者多个或门单独使用时逻辑运算顺序与输入值的顺序对结果无影响。因此

当我们需要多个条件同时满足时使用与门并接；

当我们需要在多个可能的条件中选择其中一个条件满足时使用或门并接。

卡诺图与布尔与或式卡诺图是一个简单分析2到4个输入变量的逻辑电路的真值表格。头行与头列分别表示每个输入变量的所有可能取值（通常是两个输入变量一组出现在同一行或列）。行与列的交点的值表示对应行与列的输入变量的情况的真值指派。例如在四元卡诺图中

x,y\z,w 00 01 10 11 00 0 0 0 0 01 0 1 1 1 10 0 0 0 1 11 0 1 0 0 第三行第四列表示当输入值x,y,z,w分别为1,0,1,1时输出值为1。因此我们可以合取所有输入条件：

xy'zw以此类推我们可以得出其他使得输出值为1的条件：

x'yz'w

x'yzw'

x'yzw

xyz'w然后我们求出五个逻辑表达式的析取可得该逻辑电路的布尔与或式：

x'yz'w+x'yzw'+x'yzw+xy'zw+xyz'w简化布尔表达式设A为任意逻辑表达式，b为任意逻辑变量。根据运算定律，我们有

Ab+Ab'=A(b+b')=A1=A因此我们如果能在布尔表达式中找出一组A与b，我们就可以化简这一部分表达式为A。例如在上例中的布尔表达式里，我们有

x'yzw'+x'yzw=x'yz (A=x'yz, b=w)

x'yz'w+xyz'w=yz'w (A=yz'w, b=x)代回原式子，我们有

x'yz+xy'zw+yz'w根据分配律，我们可以根据实际需要化简含y或者含w的单项式。如果化简y，整理后可得

y(x'z+z'w)+xy'zw此逻辑电路需要3个非门，6个与门和2个或门。读者可以自行验证结果。

虽然布尔表达式并不一定能给出最优化的电路设计，但是可以在后续关卡中帮助思考如何设计出符合条件的逻辑电路。

1.X 答案

与非门非门与门或门或非门高电平第二刻异或门三路与门三路或门同或门

2. 运算与存储

目标此阶段玩家需要使用逻辑门以及其他相关元件构造运算器和内存作为基础原件来构造CPU。

2.1 二进制

二进制是一种进位计数系统，计数时每达到2便前进一位，因此每个二进制数用符号0和1表示并且每第N位数表示二的N-1次幂。若a,b,c,...表示二进制位值，则二进制数abc表示

a*2^2+b*2^1+c*2^0=4a+2b+c因此十进制数7在二进制表示下为111（因为7=4+2+1）。任何十进制数和二进制数之间的转换都可以通过2的非负整数幂级数的运算来求出结果。

2.2 比特与字节

比特是二进制数位。比特（bit）同时也是一种描述两种等可能状态信息度量单位，例如0与1。一比特信息量等于确定抛一次硬币时正面还是反面向上所需要的信息量。八个比特组成的一个二进制数称为一个字节（Byte或B）。一个字节可以存储8比特的信息量，因此包括2^8=256个等可能状态。更大的字节单位有KB、MB和GB等。

2.3 短路

短路指的是一个电路中两端电压差有零电阻连接，例如一根导线直接连接电源两侧。在逻辑电路中，高电位为1低电位为0，如果在不同信号的输入端之间用导线连接会造成信号冲突导致短路——是常见的一种运行错误，应避免。其中一个常见的解决方式是在多个输入端之间用或门连接，或者用电路开关控制信号流动。

2.4 延迟线

延迟线指的是信号在从输入端发送到输出端接收的过程中具有的时间差现象。尽管大多数时候延迟现象造成信号传输效率的降低，但是有控制地延迟线路可以很好地用来存储信息以便之后调用。

2.5 回路

在逻辑电路中，回路是闭合线路。因此回路中一个点的输入会影响该点的输出。回路通常会造成电路瘫痪，因为回路点的输入与输出没有确定的状态。但在回路中添加延迟元件是可以的，因为信号的输入会被延迟从而在同一时刻不影响输出。

2.6 竖式加法运算

竖式加法运算是一种两个数进行加法的便捷手算方式，将两个数的位数对齐并依次相加，得到的结果对齐写下来（称为加和位）。如果达到进制数后向前进位，也就是把进位数加到下一位中。十进制数加法中逢十进一，0至9中任意两个数相加最高为18，因此最高进位为1。在二进制中逢二进一，0至1中任意两个数相加最高为2，即二进制中的10。因此在二进制中如果产生进位，那么加和位的结果必然是0。利用这一点可以巧妙地设计二进制数的全加器。例如在十进制中我们有

568+273=71311+11=841

2.7 负数的表示

由于逻辑电路输出只有两种状态，在一字节中表示负数的时候需要腾出额外的一个比特用来记录数字的正负性。因此在计算机中二进制的负数有各种各样的表示——其中补码最为常见。

模运算模运算指的是整数在同样的除数下所得的余数之间的运算。如果两个整数在同一个除数下的余数相同，则称这两个整数对于该除数同余，记为a=b (mod n)——a,b 为整数，n为除数。模运算加法有一个基本性质：两个整数相加所得的整数的余数等于这两个整数的余数相加所得的余数。因此模运算中同余的整数可以相互替换。

在3-bit数中我们只能表示0至7八个数。小于0或者大于7的数我们只能在钟盘上表示它们的余数。但根据同余加法原理，钟盘上的余数可以被任意同余的整数所取代而不影响模运算原有的加法性质。例如5+4=9，即二进制101+100=1001。9的余数关于除数8为1，二进制数1001前三位001恰好是余数1。-3与5同余，20与4同余，20-3=17与1同余，恰好与5+4=1相同。

因此我们可以规定钟盘左半部分大于3的余数表示负数-4至-1。其余右半部分表示0至3不变。这样我们就有了表示-4至3的3bit数。相当于最高位由4变为了-4。如果我们要计算3-1=2那么只需要求出3+7=10，其中10的余数是2。同样地，2-3=-1 可以看作是2+5=7，其中7与-1同余。

补码因此要求出任意一个数的相反数，我们有-a=0-a=8-a=7+1-a=(7-a)+1。其中7-a在二进制中表示为111-a，恰好就是二进制数a取反的过程（a有1被减为0，a有0保留下1）。因此对二进制数求相反数等价于求该二进制数的按位非后加1——这个数被称为该二进制数的补码。

2.8 编码器与解码器

编码器是将2^N个线路按顺序汇编成N位二进制数的一个电子元件。解码器与编码器工作相反，是一个把N位二进制数按顺序分解为2^N个线路的电子元件。如左图所示是2-bit编码器，将四种电路按顺序从00到11编码。左边四个输入从上到下分别表示0至3，右边输出从上到下分别表示从低位到高位组成的二进制数。虽然编码器不是过关必需元件，但是在之后的沙盒模式中可以启发玩家创造更复杂的模板。

2.9 运算逻辑单元

运算逻辑单元是一种运算元件，用来处理二进制数与其按位运算。要进行一次运算需要给入指令与二进制数。加法运算是常见运算之一，其余常见运算有减法和按位与或非等。

2.10 存储器

存储器是计算机的主要元件之一，用于存放数据。根据存储目的与形式可以分为寄存器、内存与外存。寄存器主要用于存储运算过程中所得且将要使用的数据，寄存器具有即时小量的存储特征。内存是计算机内部嵌有的存储大量数据的元件，用以存放大量的数据以便在合适的时机调用，与寄存器不同，内存具有短期大量的存储特征。外存是独立于计算机本身的存储元件，它可以长期大量存储数据并在不同的计算机之间进行数据交汇，例如硬盘与光碟。

2.11 计数器

计数器是CPU模板中的元件之一，用于记录或调用程序运行地址。和寄存器一样可以被读写以控制程序运行轨迹。在未来关卡中玩家需要通过改写计数器来构造条件判定满足时程序需要运行的轨迹。

2.X 答案

循环依赖延迟线奇变偶不变1位取反器成对的麻烦奇数个信号半加器全加器信号计数加倍1位开关8位非8位或8位加法器相反数数据选择器总线优雅存储存储一字节计数器1位解码器3位解码器逻辑引擎小盒子

3. 处理器架构

目标本章节需要玩家使用上章节已构造的元件来构造一个CPU类型：Overture。包括寄存器、运算元件、条件判断元件、计数器以及程序板等的安装。

3.1 元件工坊

元件工坊是在该游戏中制作元件的地方。玩家可以把制作好的元件用在游戏关卡或其他元件的制作里。元件的布局取决于制作元件时摆放的零件位置。同时玩家可以调整输入与输出的标签以及使用探针显示元件内部的信号。若要构造新元件，玩家需要点击“切换线路图”图标并点击“新建电路图”，然后双击想要编辑的电路图进行编辑。

3.2 条件判断

条件判断是一种逻辑运算——判断一个二进制数是否满足某个等式或不等式。在CPU架构中条件判断可用于操纵程序的运行轨迹——跳转到对应的代码地址，这可以通过对计数器的复写而实现。以下是常见的等式与不等式的性质：

三分律：若x,y为整数，则x<y、x=y或x>y;

若x,y为整数，则

自反性x=x对称性若x<y，则y>x若x=y，则y=x若x>y，则y<x传递性若x<y且y<z，则x<z若x=y且y=z，则x=z若x>y且y>z，则x>z若x,y,a为整数，则

若x<yx=yx>y所有ax+a<y+ax+a=y+ax+a>y+aa<0ax>ayax=ayax<aya=0ax=ay=0ax=ay=0ax=ay=0a>0ax<ayax=ayax>ay利用上述性质我们可以简化等式或不等式来方便我们用已有的条件判断指令。例如我们要判断x=5，可以先改写为x-5=0，然后把指令“=0”与输入“x-5”给入条件判断元件。

3.3 程序

程序是一系列用于执行的指令编码。每个编码都有其对应的地址被计数器记录。写入程序的过程被称为编程。在下一章节中玩家将练习简单的编程。例如如果玩家想对输入的两个值a与b进行加法运算，玩家可以首先写两行允许CPU复制输入值a与b到寄存器1，2的代码，然后写一行进行加法运算的代码，最后写一行保存在寄存器3的结果送到输出端的代码。

3.4 立即数

立即数是程序指令自身的二进制数编码，不同于存储器所存储的数据。例如如果玩家想要把一个值存入某个寄存器，该玩家可以使用立即数模式并直接把要复制的值写在程序里。

3.5 图灵完备

图灵完备是指一个数据指令系统（例如计算模型或计算机程序）可以模拟任何图灵机。图灵机是一个假想机器，该机器可以读取一个无限长纸带上的符号并根据现有状态可以改写符号、移动纸带或改变状态。例如一个对二进制数求相反数的图灵机（初始状态为取反，起始位置在左边第一个方格）：

现有状态现有符号写入符号移动方向下个状态取反01向右取反取反10向右取反取反空空向左加一加一01向左重置加一10向左加一加一空空向右停止重置00向左重置重置11向左重置重置空空向右停止例如数字10100，我们有

第0步空10100空取反，1第1步空00100空取反，0第2步空01100空取反，1第3步空01000空取反，0第4步空01010空取反，0第5步空01011空取反，空第6步空01011空加一，1第7步空01010空加一，1第8步空01000空加一，0第9步空01100空重置，1第10步空01100空重置，0第11步空01100空重置，空第12步空01100空停止，0得出结果为01100，符合预期。

3.X 答案

注意：图里使用的模块元件构造可以参考第X章内容。

算数引擎条件判断寄存器之路指令解码器计算单元程序立即数图灵完备

X. 元件制备

逻辑运算单元8路或门条件判断指令解码器

Source: https://steamcommunity.com/sharedfiles/filedetails/?id=3054134872

Turing Complete Guide 157