x86 - 图灵完备的字母数字 x86 指令集(子集)

Question

我希望创建一个最小的、计算通用的字母数字 x86 操作码子集。最终我希望子集包含尽可能少的指令，如果有多个最小子集，我也想知道。该子集应该能够模拟可以用整个字母数字指令集编写的任何程序。说明应仅涵盖与字符“A-Z”、“a-z”和“0-9”对应的说明。

到目前为止我认为一个 push , pop , inc , dec , cmp , 和 je就足够了，但我确定还有一个较小的集合。我如何证明我生成的集合能够使用所有字母数字指令模拟任何程序？我如何证明这样的集合是最小的？有谁知道这样的指令子集是否存在？

Answer 1

我不确定我是否明白你的问题，尤其是关于“字母数字”的部分，但我想指出的是，众所周知， mov 和 xor 图灵完备。