Ram*_*ujo 15 algorithm programming-languages
多年前,我听说有人要证明每个计算机程序只需要三个指令即可解决:
我想听听你的意见.我的意思是将任何算法表示为计算机程序.你同意吗？
sle*_*man 20
没必要.最小的理论计算机只需要一条指令.它们被称为One Instruction Set Computers(简称OISC,有点像最终的RISC).
有两种类型.第一种是理论上"纯粹"的一种指令机器,其中指令真正像普通CPU中的常规指令一样工作.指令通常是:
subtract and branch if less than zero
或其变体.在维基百科的文章有此单指令如何可以用来编写模仿其他指令代码示例.
第二种类型在理论上并不纯粹.这是转移触发的架构(维基百科再次,抱歉).这个系列的架构也被称为移动机器,我自己设计和制造了一些.
有些人认为移动机器作弊,因为机器实际上只有所有常规指令,它们是内存映射而不是操作码的一部分.但移动机器不仅仅是理论上的,它们是实用的(就像我说的,我自己建造了一些).Maxim甚至还推出了一系列商用CPU:MAXQ.如果你看一下MAXQ指令集(它们称之为传输集,因为实际上只有一条指令,我通常称之为寄存器集),你会发现MAXQ汇编看起来更像是一个基于标准累加器的架构.
这是图灵完整性的结果,这是几十年前建立的.
着名的计算机科学家阿兰·图灵证明,任何可计算的函数都可以使用图灵机来计算.图灵机是一种非常简单的理论设备,它只能做一些事情.它可以读取和写入磁带(即存储器),保持内部状态,该内部状态由从存储器读取的内容改变,并使用内部状态和最后一个读取存储器单元来确定在读取下一个磁带之前移动磁带的方向记忆细胞.
赋值,条件和循环的操作足以模拟图灵机.读写内存和维护状态需要分配.根据状态和内存内容更改磁带的方向需要条件和循环.事实上,"循环"比实际需要的高一些.所有真正需要的是程序流可以以某种方式向后跳.这意味着您可以根据需要创建循环,但语言不需要具有显式循环结构.
由于这三个操作允许模拟图灵机,并且已经证明图灵机能够计算任何可计算的功能,因此任何提供这些操作的语言也能够计算任何可计算的功能.
编辑:并且,正如其他回答者指出的那样,这些操作不需要是离散的.您可以制作一条指令来完成所有这三件事(分配,比较和分支),使其可以单独模拟图灵机.