前几天grapeot叫我帮他看一些体系结构的题，其中有一道题如下：

ISA Design:Describe an instruction set that is both minimal and can support any computation.

这道题的意思是设计一个计算机指令系统（Instruction Set Architecture, ISA），要求最少指令，并且要支持任何运算。

当时，由于我本人是做逻辑设计和验证的，凭直觉以及数理逻辑的知识，知道任何复杂的逻辑（包括计算机硬件系统）都是可以通过与非（NAND）或者 或非（NOR）堆出来的，而软件能够实现的运算，必然也可以通过硬件实现，因此，我觉得最简指令集就是一条 NAND指令 或者 NOR指令 。当然，这指令的操作数可以是三个。比如 NAND b,b,a，就是将b、a与非赋给a。

但是，我当时不太放心，而我这学期恰好学了可计算性（其实不算学，就去了一两节课）和计算复杂性。因此，我考虑了尝试用可计算理论来解决，根据我们学的可计算理论，任何可计算的问题都可以通过以下四条指令编程实现：

①自加指令：V=V+1

②自减指令：V=V-1

③空指令：   V=V

④条件跳转指令：if V ≠ 0,GOTO L

对于这个答案，我比较自信能够完成所有通用计算。我一直搞不明白的是为什么要加空指令（现在想可能是为了可计算理论里面证明来用的）。

昨天，和雨聊到自动机的话题，我又想到了这道题，当时我把我的想法说了，但貌似雨不太理解，并且说道如何实现除法操作，我自己都被搞晕了。只是我们都觉得也许从图灵机角度出发会比较好（图灵机其实就是一些状态机的跳转，这些状态机可以用四元组或者五元组构成）。今天恰好不想复习（哎，后面三门连续的考试怎么办啊怎么办），于是又想了下这个问题，但还是想不太明白。

只好放出最后一招，放狗搜，凭直觉，我觉得肯定有单指令的计算机，于是直接搜“single instruction computer”，搜到了wikipedia的词条OISC（one instruction set computer）。看了下，感觉比较靠谱，在这里分享下：

维基上把一条指令的计算机主要分成了四种：

①减并且小于等于0跳转（Subtract and branch if less than or equal to zero）

②减并且为负数跳转（Subtract and branch if negative）

③Reverse subtract and skip if borrow（这个貌似翻译成起来很拗口，并且我也没看太懂，所以不翻译）

④Move（不过看了下，貌似它需要有相当于一个ALU功能的ROM，其实这个ROM相当于图灵机里的状态转化的集合F）

在这里，我只解释下第一种，第二种与第一种类似，第三种没看懂，第四种，感觉就是个图灵机。

首先，解释下subleq("SUbtract and Branch if Less than or EQual to zero")的定义，其实它相当于两条指令：

subleq a, b, c   ; Mem[b] = Mem[b] - Mem[a]
                     ; if (Mem[b] ≤ 0) goto c

下面用subleq可以完成一些其他运算，通过部分示例来说明它是可以完成通用计算的：

  • 无条件跳转 
        JMP c ==    subleq Z, Z, c   ; Z is a location previously set to contain 0
  • 加法操作 
        ADD a, b == subleq a, Z
                subleq Z, b
                subleq Z, Z
  • MOVE操作 
        MOV a, b == subleq b, b
                subleq a, Z
                subleq Z, b
                subleq Z, Z

    从上面，我们几条指令的翻译，我们可以比较自信的下结论，subleq是比较靠谱的。

从上面几个指令集，很容易发现，貌似条件跳转是一个很核心的东西。

不过，我还是想，一个NAND指令还是可以实现单指令计算机的，其他算术和逻辑运算肯定是能用NAND完成的，现在只剩下一个条件跳转了。但凭我直接，条件跳转和硬件中的二选一很像，既然，二选一可以用NAND实现，条件跳转肯定也可以。

ps1：更多关于一条指令的计算机请看google上single instruction computer的搜索结果.

ps2：我上面说的东西肯定有很多错误，欢迎指正。