algorithm - 用计算机程序解决任何问题的最小指令集

Question

几年前，我听说有人要证明每个计算机程序都可以只用三个指令来解决:

• 作业
• 有条件的
• 循环

我想听听您的意见。我的意思是将任何算法表示为计算机程序。你同意吗？

Answer 1

不需要。最小的理论计算机只需要一条指令。他们被称为One Instruction Set Computers (OISC for short, kinda like the ultimate RISC) .

有两种类型。第一个是理论上“纯”单指令机，其中的指令实际上像普通 CPU 中的常规指令一样工作。指令通常是:

subtract and branch if less than zero

或其变体。 wikipedia article举例说明如何使用这条指令来编写模拟其他指令的代码。

第二种是不理论上纯的。这是 transfer triggered architecture (又是维基百科，抱歉)。这一系列架构也被称为移动机器，我自己设计并构建了一些。

有些人认为移动机器作弊，因为机器实际上拥有所有常规指令，只是它们是内存映射的，而不是操作码的一部分。但是移动机器不仅仅是理论上的，它们是实用的(就像我说的，我自己 build 了一些)。甚至还有一个由 Maxim 构建的商用 CPU 系列:MAXQ .如果您查看 MAXQ 指令集(他们称之为传输集，因为实际上只有一条指令，我通常将其称为寄存器集)，您会发现 MAXQ 程序集看起来很像基于标准累加器的架构。