图灵完备 8 元件 COND - 加法器解法
前言
头像来自 Steam Turing Complete profile。
Info
没有玩过图灵完备“条件判断”关卡的读者可能比较难理解。
作者尽量详尽表述。
勘误
在深入研究文本之前，请务必注意可能存在一些 语法错误 ，这可能是由于翻译错误、打字错误或作者独特的写作风格。
如果你有疑问或者建议，欢迎在评论区留言，或通过邮箱 shetty@shettydev.com 联系。
成品图
如图所示，蓝色元件一共 8 个，并且可以通过条件判断关卡测试。
这里展示一下我的成就：
作者并没有参考任何解法，纯粹是自己尝试出来的。
所以我也不知道我的解法是否已经存在了。
关卡分析
通关条件
读一遍题目：
这个关卡的输入有一个数值和 3 个条件位。
如下图所示，根据 3 个条件位的组合确定要进行的判断类型。并根据所选判断类型检查输入的数值，如果判断为真则输出 🟢 ，否则输出 🔴。
| 3 位代码： | 以下条件满足时，给出 🟢： |
|---|---|
| 🔴🔴🔴 | Never（从不） |
| 🔴🔴🟢 | value == 0 |
| 🔴🟢🔴 | value < 0 |
| 🔴🟢🟢 | value <= 0 |
| 🟢🔴🔴 | Always（总是） |
| 🟢🔴🟢 | value != 0 |
| 🟢🟢🔴 | value >= 0 |
| 🟢🟢🟢 | value > 0 |
常规思路
两个输入全是 8 位的，分别是条件和数值，其中条件只用到 3 位。
使用 8 位分线器将条件输入分成 8 个 1 位输入，取前三位接入 3 位解码器，此时 8 种条件转化为 8 个输入，每种条件只会激活一条路。
使用 8 位分线器将数值分成 8 个 1 位输入。
注意到题目中前 4 个条件与后 4 个条件是非关系，因此只需要处理 4 种情况：
| 条件 | 如何满足 |
|---|---|
| Never | 低电平 0 (A) |
| value == 0 | 数值的所有位 == 0 (B) |
| value < 0 | 数值的 128 位 == 1 (C) |
| value <= 0 | B OR C (D) |
| Always | NOT A |
| value != 0 | NOT B |
| value >= 0 | NOT C |
| value > 0 | NOT D |
其中“数值的所有位 == 0”这一项使用多个 3 输入 OR 可以完成。
- 根据上表搭建出 8 个输出，与 8 种条件配合串联 1 位 S （开关），再连接到输出。
这种方法用了我足足 21 个蓝色元件 😅。
下面来看看 8 元件解法吧！
再放一遍成品图：
原理分析
8 位 ADD 判断
进位输出
8 位 ADD 有一个进位输出，结果需要进位输出高电平，否则低电平。
这个特性是本次解法的核心。
下表揭示了进位端的意义，其中 ORIN 表示原输入，NOT 是 8 位取反，NEG 是取相反数：
| ADD 输入 1 | ADD 输入 2 | ADD 进位端高电平含义 |
|---|---|---|
| ORIN | ORIN | ORIN < 0（本次解法不使用） |
| NOT ORIN | NOT ORIN | ORIN >= 0 |
| ORIN | NEG ORIN | ORIN != 0 |
| ORIN | NOT ORIN | Never |
| NEG ORIN | NOT ORIN | ORIN > 0 |
只要将 Never 取反，这些结果恰好对应以下 4 种条件：
| 条件位第 3 位 | 条件位第 2、1 位 | 以下条件满足时，给出高电平 |
|---|---|---|
| 1 | 00 | Always（总是） |
| 1 | 01 | value != 0 |
| 1 | 10 | value >= 0 |
| 1 | 11 | value > 0 |
8 位 MUX 编码
8 位 MUX 的条件输入端 0、1 分别代表输出输入 1、输入 2。
MUX 的特性使得它可以作为译码器，此解法中使用两个 8 位 MUX 组成 2 位译码器。
将两个 MUX 的输出连接到 8 位 ADD 的两个输入。
译码参考下表：
| MUX 1 条件输入 | MUX 2 条件输入 | MUX 1 输出 | MUX 2 输出 | ADD 输出高电平条件 |
|---|---|---|---|---|
| 0 | 0 | ORIN | NOT ORIN | Never |
| 0 | 1 | ORIN | NEG ORIN | ORIN != 0 |
| 1 | 0 | NOT ORIN | NOT ORIN | ORIN >= 0 |
| 1 | 1 | NOT ORIN | NEG ORIN | ORIN > 0 |
NOR 进位
译码表格中除了 00 这一项，其余都满足了要求。
如何单独将 00 的结果取反，而不影响其他结果？并且保证不破坏 ADD 进位端是输出端的条件。
ORIN 是一个 8 位的数，ORIN + (NOT ORIN) 的结果永远是 11111111，因此进位端永远是 0。
注意到 ADD 存在一个进位输入，提供进位输入高电平，计算结果变为 1 + ORIN + (NOT ORIN)，结果是 100000000，发生进位，成功将 00 对应的输出取反。
使用 NOR 控制只有条件 2、3 位输入为 00 时，提供进位输入。
此时下表的条件已经满足：
| 条件位第 3 位 | 条件位第 2、1 位 | 以下条件满足时，给出高电平 |
|---|---|---|
| 1 | 00 | Always（总是） |
| 1 | 01 | value != 0 |
| 1 | 10 | value >= 0 |
| 1 | 11 | value > 0 |
XNOR 条件取反
条件位第 3 位为 0 时，将上表的输出取反即可。
但是不能使用 S（开关），这用到太多元件了！
我们希望条件位第 3 位为 0 时，输出不变，为 1 时，输出取反。
只需 1 个 XNOR 就可以满足，输入分别是条件位第 3 位和 ADD 进位输出，此时输出满足题目要求。
至此，8 元件 COND 完成。
- Title: 图灵完备 8 元件 COND - 加法器解法
- Author: Shetty Yttehs
- Created at : 2025-06-15 23:05:12
- Updated at : 2025-06-27 23:58:42
- Link: https://blog.shettydev.com/2025/06/15/turing-complete-simple-cond/
- License: This work is licensed under CC BY-NC-SA 4.0.
