图灵机 - The mini wiki

模拟计算机，是计算机的一种形式，它使用电子的，机械的或液压的量等物理现象的不断变化的方面来模拟所要解决的问题。相反，电子计算机象征性地表示不同数量，因为它们的数值发生了变化。由于模拟计算机不使用离散化，而是使用连续值，所以过程不能像精确等同那样可靠地重复进行，就像它们可以使用图灵机一样。与数字信号处理不同，模拟计算机不受量化噪声的影响，但受噪声的限制。

在计算复杂性理论中，交互式证明体系是一类计算模型。像其它计算模型一样，我们的目标是对一个形式化语言L，和一个给定的输入x，判断x是否在L中。交互式证明体系由两个实体：验证者和证明者组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。

在可计算性理论中，总是停机的机器也叫做判定器或全图灵机是对所有输入总是停机的图灵机。

兰顿蚂蚁是细胞自动机的例子。它由克里斯托夫·兰顿在1986年提出，它由黑白格子和一只“蚂蚁”构成，是一个二维图灵机。兰顿蚂蚁拥有非常简单的逻辑和复杂的表现。在2000年兰顿蚂蚁的图灵完备性被证明。兰顿蚂蚁的想法后来被推广，比如使用多种颜色。

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数。直觉上递归函数是"可计算的"。事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数。递归函数与原始递归函数相关，而且递归函数的归纳定义建立在原始递归函数之上。但不是所有递归函数都是原始递归函数——其中最著名的是阿克曼函数。

在计算复杂性理论中，交互式证明体系是一类计算模型。像其它计算模型一样，我们的目标是对一个形式化语言L，和一个给定的输入x，判断x是否在L中。交互式证明体系由两个实体：验证者和证明者组成，两者都可以看作是某类图灵机。而它的计算过程为：给定了输入x，通过验证者和证明者之间交换信息，最终，由验证者来根据证明者给出的信息，判断给定的输入是不是在语言L中。

λ演算是一套从数学逻辑中发展，以变数绑定和替换的规则，来研究函数如何抽象化定义、函式如何被应用以及递归的形式系统。它由数学家阿隆佐·邱奇在20世纪30年代首次发表。lambda演算作为一种广泛用途的计算模型，可以清晰地定义什么是一个可计算函式，而任何可计算函式都能以这种形式表达和求值，它能模拟单一磁带图灵机的计算过程；尽管如此，lambda演算强调的是变换规则的运用，而非实现它们的具体机器。

单一指令计算机也称最简指令集计算机，它是一种抽象计算机，该计算机只有一条指令。巧妙地选取这一条指令，并且给予无限的资源，单一指令计算机就能成为和其他多指令计算机一样的图灵机。在教学上，这种计算机被推荐来帮助理解计算机架构，同时，也能用它来研究计算机的结构模型。