圖靈完整的字母數字x86指令集（子集）

Question

我期待創建一個最小的，計算上通用的字母數字x86操作子集。最終，我希望子集包含儘可能少的指令，如果有多個最小子集，我也想知道。子集應該能夠模擬任何可以用整套字母數字指令寫入的程序。說明應僅涵蓋與「A-Z」，「a-z」和「0-9」字符對應的說明。

到目前爲止，我認爲一個push，pop，inc，dec，cmp和je就足夠了，但我敢肯定有一個較小的一套。我怎麼能證明我生成的一個集合能夠使用所有的字母數字指令來模擬任何程序？我怎麼能證明這樣一個集合是最小的？有誰知道這樣的指令子集是否存在？

Answer 1

這只是一條指令！這裏的證明

http://en.wikipedia.org/wiki/One_instruction_set_computer

爲什麼？僅僅因爲「指令」是一個與機器相關的概念。你不能僅僅因爲沒有這樣的通用/絕對/原子指令就定義一小組指令：它全部取決於底層硬件：實際上，「真正的」圖靈機是一種數學概念（一組規則）而不是物理機器

Answer 2

我不確定我是否有問題，特別是關於「字母數字」的部分，但我想指出，衆所周知，mov和xor都是圖靈完整版。