图灵完备攻略：算术运算与存储器详解
图灵完备攻略：算术运算与存储器详解
本文是一篇关于图灵完备攻略的教程文章，主要介绍了两个部分的内容：算术运算和存储器。文章详细描述了多个关卡的具体实现方法，包括二进制运算、加法器、存储器等基础电路的搭建。
图灵完备攻略2.算术运算& 3. 存储器
第2部分15关，关卡名为二进制速算、成对的麻烦、奇数个信号、信号计数、半加器、加倍、全加器、8位或、8位非、8位加法器、负数、相反数、1位解码器、3位解码器和逻辑引擎。
第3部分11关，关卡名为循环依赖、延迟线、奇变偶不变、1位开关、1位取反器、数据选择器、总线、优雅存储、存储1字节、小盒子和计数器。
这两部分是交叉进行的，因此合并在一起。
关卡13. 二进制速算
内容略，这一关不是画电路图的，需要你自行熟悉二进制数。
关卡14. 成对的麻烦
4个输入，至少两个为1时，输出为1。
关卡15. 奇数个信号
关卡16. 循环依赖
关卡17. 信号计数（搭建4位加法器元件）
这一关有点难度，实际上这是一个4位加法器，个人觉得这个关卡应该放到后面。
首先，对上面两个输入信号求和，可以用2位加法器（又叫半加器）进行求和。具体实现是并联的XOR和AND，XOR输出求和的个位（第1位），AND输出求和的进位（第2位）。
然后再来一组半加器，对下面两个输入信号相同处理。这样，我们读取了所有的四个输入值，得到两个第1位和两个第2位。
然后对两个第1位用半加器求和，这样只剩下一个第1位（导出到输出的第1位），剩下三个第2位。
先对三个第2位中的其中两个求和，这样剩下两个第2位和一个第3位。
再对两个第2位求和，这样只剩下一个第2位（导出到输出的第2位）和两个第3位。
最后对两个第3位求和，得到一个第3位（导出到输出的第3位）和一个第4位输出（由于4路输入最大值为100，又写作0100，第4位必然为0，所以这个AND元件没有必要画上去）。
关卡18. 半加器（搭建2位加法器/半加器元件）
本质上是一个2位的加法器：0+0=00、0+1=01、1+1=10。用并联的XOR和AND实现，XOR输出个位，AND输出进位。
关卡19. 延迟线
这一关是让你熟悉延迟元件的。游戏号称只需要NAND元件就能搭建所有计算机电路，但是这里突然新出现一个延迟元件，初看似乎“作弊”，违背初衷。但实际上，延迟元件也可以通过门电路元件搭建，只需要让信号多走一个回路，就能实现延迟，不算违背初衷，只是没把延迟元件的原理展示出来。
关卡20. 加倍
二进制数加倍，只需要移动一位即可，即数字最后加个0。
关卡21. 全加器（搭建3位加法器/全加器元件）
全加器实际上就是一个3位加法器，原理和上面第17和18关卡的2位加法器（半加器）和4位加法器相同。
关卡22. 奇变偶不变
这一关描述比较含糊，没有参考的情况下也有点考验智力，但实际上看答案就能很容易明白。提示需要循环依赖，那么循环依赖只能在一个延迟元件前后循环，不能接到输入和输出。确定这个原则后，剩下的就是选取合适的门电路元件了。
关卡23. 1位开关
新引入一个1位开关，用其搭建异或门（XOR）。实现起来很简单，但这里就和之前的延迟元件一样，也没有介绍这个新元件的内部构造。
关卡24. 1位取反器
关卡25. 8位或（搭建8位或门元件）
关卡26. 8位非（搭建8位非门元件）
关卡27. 8位加法器（搭建8位加法器元件）
关卡28. 负数
和第13关二进制速算一样，具体内容略，这一关是让你熟悉有符号数字的二进制表示的。
关卡29. 数据选择器（搭建8位数据选择器元件）
关卡30. 相反数
一个有符号数x，用8位非门取反之后，数值变成了-x-1，因此再+1即可得到-x。
下图是用1位元件搭建的电路，实际上+1步骤也可以用8位加法器元件实现，不过如果把细节展开，两者本质是一样的。
关卡31. 总线
为了美观，我移动了输入元件的位置。然后特地把总线突出出来，就是中间那根。
关卡32. 优雅存储（搭建1位存储器元件）
这一关也有点难度，相关知识点在书里叫做“锁存器”。
下图是用“D型锁存器”实现的，只用4个元件。其核心思想是右边两个NAND门的输入和输出端交叉互联。
至于为什么这种交叉互联能达成“锁存”的效果，可以参考书上解释。我个人的理解如下：
前面的关卡在使用门电路时，我们都是用两个输入端的状态去判断输出端的状态，实际上，一个输入端+输出端的状态，可以用来判断另一个输入端的状态。如果另一个输入端的状态可0可1，那么反过来，无论这个输入端怎么变化，输出端状态都会维持不变。
关卡33. 存储1字节（搭建8位寄存器元件）
这里用到了新元件，八个1位存储器，按照我的理解，就是上个关卡的锁存器。
关卡34. 1位解码器（搭建1位解码器元件）
关卡35. 3位解码器（搭建3位解码器元件）
最简单粗暴的解法，反而效率最高。
关卡36. 逻辑引擎
这一关的电路实现了四个功能，根据指令字节对两路输入字节取OR、NAND、NOR、AND。后续会再在此基础上添加两个新功能，求和和求差。
关卡37. 小盒子
这一关的难点是怎样布线，我把输入元件从左边移到了右下角输出元件的上边。