描述数

描述数是图灵机理论中出现的数字。它们与哥德尔数非常相似，在文献中也偶尔被称为哥德尔数。给定一些通用的图灵机，每台图灵机都可以在该机器上给其编码，并分配一个数字。这就是机器的描述号。这些数字在阿兰-图灵对停止问题的不可判定性的证明中发挥了关键作用，在推理图灵机时也非常有用。

假设我们有一台图灵机M，状态为q1,...qR，磁带字母表上有符号s1,...sm，空白处用s0表示，转换时给出当前状态、当前符号和执行的动作（可能是覆盖当前磁带符号，向左或向右移动磁带头，也可能根本不移动），以及下一个状态。在阿兰-图灵描述的原始通用机器下，这台机器将被编码为它的输入，如下所示。状态qi由字母'D'跟着字母'A'重复i次来编码（单数编码），磁带符号sj由字母'D'跟着字母'C'重复j次来编码，转换是通过给出状态、输入符号、要写在磁带上的符号、移动方向（用字母'L'、'R'或'N'表示，代表左、右或不移动）和要进入的下一个状态来编码，状态和符号的编码方式同上。因此，UTM的输入由分号分隔的过渡组成，所以它的输入字母表由七个符号组成，'D'、'A'、'C'、'L'、'R'、'N'和'；'。例如，对于一个非常简单的图灵机，它永远在其磁带上交替打印0和1。状态：q1，输入符号：空白，动作：打印1，向右移动，下一状态：q2状态：q2，输入符号：空白，动作：打印0，向右移动，下一状态：q1让空白为s0，'0'为s1，'1'为s2，机器将被UTM编码为。daddccrdaa;daaddcrda。但是，如果我们将七个符号'A'分别替换为1，'C'替换为2，'D'替换为3，'L'替换为4，'R'替换为5，'N'替换为6，'；'替换为7，我们将得到图灵机的编码为一个自然数：这就是图灵通用机器下该图灵机的描述数。因此，上面描述的简单图灵机的描述号是313322531173113325317。对于每一种其他类型的通用图灵机都有一个类似的过程。通常没有必要以这种方式实际计算描述号：重点是每个自然数都可以被解释为最多一个图灵机的代码，尽管许多自然数可能不是任何图灵机的代码（或者换一种说法，它们代表没有状态的图灵机）。对于任何图灵机来说，这样的数字总是存在的，这通常是重要的事情。

说明数在许多不可知性证明中起着关键作用，例如证明停止问题是不可知的。首先，自然数和图灵机之间的这种直接对应关系的存在表明，所有图灵机的集合是可数的，由于所有部分函数的集合是不可数的无限的，肯定有许多函数不能被图灵机计算。通过利用类似于康托尔对角线论证的技术，可以展示这样的不可计算的函数，例如，特别是停止问题是不可判定的。首先，让我们用U(e,x)表示通用图灵机的动作，给定一个描述数e和输入x，如果e不是有效图灵机的描述数，则返回0。

现在，假设有一些能够解决停止问题的算法，即一个图灵机TEST(e)，它给定某个图灵机的描述号，如果图灵机在每个输入上都停止，则返回1；如果有一些输入会导致它永远运行，则返回0。通过结合这些机器的输出，应该可以构建另一个机器δ(k)，如果TEST(k)为1，则返回U(k,k)+1，如果TEST(k)为0则返回0。既然δ是由我们假设的图灵机建立起来的，那么它也必须有一个描述号，称之为e。因此，我们可以再次将描述号e送入UTM，根据定义，δ(k)=U(e，k)，所以δ(e)=U(e，e)。但由于TEST(e)是1，根据我们的另一个定义，δ(e)=U(e,e)+1，导致了矛盾。因此，TEST(e)不可能存在，这样一来，我们就把停顿问题解决了，因为它是不可解的。