智能 | #6 扩展二进制图灵机

文 | HW君

本文目录：

  0. 前言

  1. 扩展二进制表示法

  2. 优化细节

  3. 效率的提升

  4. 扩展二进制图灵机

  5. 结语

0. 前言

上一期《智能 | #5 一进制图灵机》我们介绍了最简单的一进制图灵机，初步窥见了这台机器所蕴含的巨大潜力。

图灵机的魅力就在于，哪怕是规则如此简单的一进制图灵机，它的数学模型和我们现代计算机也是等价的。

从这些最简单的规则出发，我们就足以能够通向现代通用计算机，直到抵达人工智能。

但一进制图灵机的模型仍然是非常低效率的，这一期我们会在这些基础的规则上再堆叠一些复杂度，以便获得更多的理论洞见。

这个过程中会引用到一些公式，但并不复杂，仅仅需要一些耐心。

这也是图灵定义的希尔伯特判定问题的「机械过程」的特点，你只需要耐心地完成一些机械的步骤，就能得到正确的结果。

但也不必迷失于细节之中，如果觉得吃力，也可以适当跳过。

1. 扩展二进制表示法

回顾一下一进制数的表示方法：

1 1；

2 11；

3 111；

4 1111；

…

例如十进制自然数4可以在图灵机中被描述成如下的一条一进制纸带：

…000011110000….

但这种一进制表示方法是非常低效的，假如我们描述十进制的10000，那就需要在纸带上写入一万个1。

为了解决大数的表示问题，这里我们引入一种称为「扩展二进制」的表示方式。

扩展二进制的基础是「二进制」。

以下为十进制数 0 到 10 的二进制表示：

然而我们并不能直接在图灵机的纸带上直接使用二进制。

因为读取头无法确定一个二进制数从何处开始和结束，也无法将两个并列的二进制数区分开。

为了能让读写头区分出一个二进制数，这里我们需要引入了一种扩展的机制。

在一进制中，图灵机可以通过数两个单独 0 之间 1 的数量来确定一个十进制数：

这样我们就有了可以被图灵机分辨的十进制 0，1，2，3，4...

其中一进制「00」和「010」所代表的十进制「」和「1」可以用来创建二进制数。

而 「0110」所代表的「2」则可以当作区分两个数的间隔，记为「,」。

而3，4，5......等其他数，则可以用来当作其它某种记号或者指令。

例如可以把 3 当作负号「-」，把 4 当作加号「+」，把 5 当作乘号「×」...等等。

假设有下面这么一段数列：

01000101101010110100011101010111100110

通过数相邻的两个之间有多少个 1，可以从一进制被转为以下的十进制数列：

10012112100311402

其中和 1 的序列构成一个二进制数，2 表示「,」，3 表示「-」，4表示「+」。

那么这段序列又可以被转换为：

9 , 3 , 4 , 4-3+0 ,

这样我们实现了用扩展二进制数来表示多个十进制数以及一些其它的符号。

2. 优化细节

扩展二进制数有一些方便的特性，可以帮我们优化数的表示。

因为转换的第一步是通过数相邻的两个之间有多少个 1，而相邻两组数会共用一个，因此在反向转换时我们可以省去前方的那个。

即扩展二进制的「」和「1」以及分隔号「,」可以依据如下规则进行处理：

0 00

1 010 10

, 0110 110

例如下面这一组十进制数列，数与数之间用逗号「,」隔开：

5 , 13 , 0 , 1 , 1 , 4 ,

首先我们将其转换为二进制数：

101 , 1101 , 0 , 1 , 1 , 100 ,

然后依据扩展二进制的规则转换，并在首尾加上无限个0，最终得到如下的一条纸带：

...00001001011010100101100110101101011010001100000...

而在这样的一种表示方法中，纸带左边前端的一长串无意义的「...0000...」是可以被忽略的。

纸带右边结尾「110」所代表的「,」，也可以把后面一长串无意义的「...0000...」给区隔开。

以及，纸带中间由两个「110」所分隔开的「0」也是可以忽略掉的。

即如下的数列：

101 , 1101 , 0 , 1 , 1 , 100 ,

可以被改写为：

101 , 1101 ,  , 1 , 1 , 100 ,

因此我们可以把纸带中间两个「110」间的那个 0 给去掉，得到：

...0000100101101010010110110101101011010001100000...

以上就是一段扩展二进制数列。

它的十进制形式是：

5 , 13 , 0 , 1 , 1 , 4 ,

3. 效率的提升

现在我们可以来考察这台扩展二进制图灵机的效率了。

如果我们使用一进制图灵机来一组十进制自然数 6 和 8 ，那么输入的纸带为：

...00001111110111111110000...

而十进制 6 和 8 的二进制数为「110」和「1000」。

即将数列「6 , 8 ,」转换为扩展二进制后的纸带为：

...000010100110100001100000...

这看上去扩展二进制似乎并没有比一进制形式更加节省空间。

但随着十进制自然数的增大，扩展二进制的优势会更加明显。

考虑十进制数 2015，它的二进制形式为「11111011111」。

那么「2015 ,」的扩展二进制纸带为：

...00001010101010010101010101100000...

如果用一进制来表示 2025，那么我需要在这里复制粘贴 2015 个1，这显然有点办不到。

因此当涉及到越大的数的时候，扩展二进制的优势就会越明显。

4. 扩展二进制图灵机

在上一期《智能 | #5 一进制图灵机》中我们展示了「一进制+1图灵机」。

那对于扩展二进制来说，也同样存在着「扩展二进制+1图灵机」。

它的状态控制器如下：

0 00 0R

0 11 1R

1 00 0R

1 12 1R

2 03 0L

2 15 1R

3 00 1R 停

3 14 0L

4 05 1L

4 14 1L

5 06 0R

5 12 1R

6 17 1R

7 03 1R

7 17 0R

这看起来和「一进制+1图灵机」相比稍显复杂，但对于大数来说仍然是要更高效的。

有耐心的朋友可以试试这台图灵机是否正常工作，注意数的结尾要加上「,」，即纸带的末尾有「110」。

同样的，我们也可以制造出一台「扩展二进制×2图灵机」。

它的状态控制器如下：

0 00 0R

0 11 0R

1 00 1R

1 12 0R

2 03 1R

3 00 1R 停

它的运算操作显然要比「一进制×2图灵机」简单高效得多。

同样我们也可以去实现「扩展二进制欧几里得算法图灵机」，但这样就有点陷于细枝末节了。

我们只需要知道「扩展二进制图灵机」和「一进制图灵机」在数学上是等价的，图灵认为它们都可以模拟人类所能进行的任何计算。

而本期介绍「扩展二进制图灵机」是因为它存在着一些更高效的表示特性，可以便于我们后续进行更深入的讨论。

5. 结语

这两期我们介绍了图灵机的基本原理，有些朋友面对这些细枝末节可能会感到迷茫。

但这其实是讨论图灵其哲学思想的必经之路。

图灵的思考是建立在严谨的数学理论之上的。

没有理论支撑的哲学思辨，容易陷入不切实际的空谈。

当然我们也不必迷失于细节之中。

如果觉得吃力，可以适当跳过。

（本章节完，敬请期待下一节）

By HW君 @ 2025-01-02