用户:LynChern/Sandbox

本文是关于计算机科学概念的，关于深奥虚拟机，请见UM-32。

通用机是模拟其类别中其他机器的程序。最常见的通用机是通用图灵机，它们是模拟图灵完备系统行为的图灵机程序。

通用机包含以下部分：

• 机器；指一种语言（例如 Brainfuck、Python、λ演算）、机器（图灵机、明斯基机）或其他计算模型。
• 程序描述；一个固定的、有限的描述，由机器执行的若干符号或状态组成。
• 一些输入程序描述；由固定程序对其进行求值。通用机可以通过保持机器和固定程序描述不变，使用任意的输入程序重新运行。

传统上，通用图灵机会在其纸带上获得输入程序描述，机器启动时其纸带以某种方式预先初始化了给定程序。通过某些输入指令“交互式”接受输入的通用机也是可以接受的。因此，通用机可以在缺乏I/O的语言中实现，前提是存在一种约定的方式，在机器运行之前可以初始化存储机制。

通用机对其实现语言的计算类别有影响。在大多数情况下，如果在给定语言中编写了一个图灵完备的通用机，那么该语言本身也是图灵完备的。然而，这并不绝对正确。有可能创建一种语言，其中唯一有效的程序就是通用机。如果情况如此，该机器或语言被认为是ℒ完备的。这样的系统是否图灵完备存在争议。一方面，是的，该系统可以模拟一个图灵完备的系统。另一方面，只有在被模拟机器的程序作为描述提供给该机器时才能这样做，没有办法将给定的机器翻译成底层机器的程序描述，只能将其翻译成被模拟机器的描述。

弱通用机

某些通用机需要特定的初始条件或其系统的推广才能具有通用性。其中一个例子是Wolfram提出的(2, 3)通用图灵机。该机器通过模拟循环标签实现通用性，但现有证明依赖于状态的无限非周期初始配置。图灵机的正式定义要求字母表中存在一个空白符号，所有单元格都初始化为该符号，这意味着在经过任何有限步之后，纸带上永远只有1个符号具有无限出现次数（即空白符号）。需要等效于图灵机纸带被初始化为多个不同空白符号（从而有多个符号具有无限出现次数）的条件的通用机违反了这一要求，因为图灵机永远无法将其纸带配置成那样（但或许能使其等效）。

需要这种空白配置的通用机可称为弱通用机。只有弱通用机是可能的系统可被视为弱图灵完备。

图灵机纸带的某些初始配置是不可计算的。考虑一个纸带，其中每个向右的单元格编号（距离0的距离）对应于图灵完备语言中程序描述的编码，单元格根据程序是否停机被初始化为0或1。这台机器可以解决图灵机停机问题，因此是不可计算的。

然而，并非所有初始配置都是不可计算的。只有一个符号的配置当然是可计算的，因为这等同于图灵机正式定义中的空白符号。一维棋盘格图案（...ABAB...）也是可计算的，其行为可以被一台具有空白符号Z且程序具有偶数和奇数分支的图灵机模拟。当遇到Z时，偶数分支将Z替换为A并切换到奇数分支，而奇数分支将Z替换为B并切换到偶数分支。请注意，虽然此机器的行为等效于用棋盘格初始化的机器，但纸带永远不会相同（因为总是有无穷多个Z和有限的A、B）。此通用过程适用于任何周期性图案。

虽然不可计算的图案是非周期性的，但非周期性图案不一定不可计算。考虑图案010010001...，其中每个连续的1前面有递增数量的零。这个图案是非周期性的，但一台拥有它的图灵机可以被一台具有空白纸带的图灵机模拟。空白符号是Z。开始时，此图案的有限部分被复制到n个零后跟1的位置。在最后一个1之后，放置n+1个A。在此初始常数部分之后，在执行过程中，当遇到A时，机器进入一个循环：将A替换为0，然后在第一个Z之后放置一个对应的A。一旦所有A都被移动，在末尾再放置一个A，并将A前面的Z与1交换。这个可计算的过程无需进行无限的初始工作就能再现非周期性图案。

依赖于不可计算初始化系统的通用机也是不可计算的。因此，当使用弱通用机证明图灵等价性时，必须证明它们能够被一台模拟通用机所在外部系统（包括图案生成）的图灵机所模拟。

通用机示例

• UT19，一个19符号通用2标签系统
• [[Grill Tag#Turing machine implementation|一个实现Grill Tag的2状态、14符号图灵机]]
• Gregušová-Korec通用明斯基机，一个37或32指令的明斯基机

外部资源

• 适用于URM的通用图灵机 一个适用于修改版明斯基机的5寄存器机器