操作系统基础 01 - 起源(一) 图灵机

发表于 | 更新于 | 分类于 ， ， | 阅读次数：

前言

本篇博文是操作系统基础系列之一；本文为作者的原创作品，转载需注明出处；

背景

在 1936 年以前，人们一直在寻求一种能够通过机器自动帮我们进行复杂运算的方法；当时的机器要么只能算加法，要么只能算乘法；我们需要一种通用的机器，能够帮我们自动的进行任意的复杂的运算；直到图灵在 1936 年的时候，提出了图灵机，一种理论，可以通过一种通用的规则使得机器自动的帮我们进行一系列(可计数范围内的)复杂的运算；

模型

基本元素

先来看一下一个模拟图灵机的装置，

可以看到，它由如下几个部分组成，

  1. 无限长的纸带(原文叫 Tape)，带有无限多个方格；且方格有个特性，就是可以被读写；
  2. Tap Head指针头，
    • 它始终指向当前的一个方格，当前方格的位置称作 current Position；
    • 它可以读取当前方格中的内容，该内容成为当前值 current Value；
    • 它可以在当前方格中写入，如果当前方格已经有内容了，擦除后重写；
  3. State，每一个 current Position 都有一个状态 State，它告诉当前的 Tap Head 该做什么，是对当前的方格进行只读或者读写？处理完以后，下一步是左移还是右移？
    A State $\to$ A Rule，每一个 State 对应一个 Rule，正是这个 Rule 告诉 Tap Head 在当前位置该如何操作；

理论

有限状态机

图灵机其实是一个带规则的有限状态机，什么是有限状态机，看一张概念图，

针对图中的每一个节点，状态机五要素如下，

  • 当前状态 current State
  • 输入
  • 规则 Rule，在当前状态下执行的规则，该规则指定 next State；
  • 输出
  • 下一个状态 next State

有限状态机，则需要在状态机上加上一个起始状态 init State 和结束状态 final State，通常 final State 有成功和失败两种状态；图灵机就是一种有限状态机

图灵机

图灵机的有限状态机有如下元素，

  1. 状态
    包含起始状态、中间状态和结束状态；起始状态用 $q_0$ 表示，结束状态用 $q_a$ 表示；
  2. 输入
    ascii 码值，输入是由 Tap Head 所读到的内容；
  3. 输出
    ascii 码值，输出是由 Tap Head 写出的内容；
  4. 移动
    ${L, R, N}$ 中的一个，其中 L 表示读写头向左移一格，R 表示读写头向右移一格，N 表示读写头不动

图灵机的规则(Rule)定义，看一个例子

current State 输入值 输出值 移动 next State
$q_0$ 1 0 R $q_1$
$q_0$ 0 0 R $q_1$
$q_1$ 1 0 N $q_a$
$q_1$ 0 0 N $q_a$

我们来解读一下这个状态机，

  • 从起始状态 $q_0$ 开始，
    • 若当前值(输入值)为 1，则用 0 覆盖当前值，指针头右移一位，然后进入 $q_1$；
    • 若当前值(输入值)为 0，则不变，指针头右移一位，然后进入 $q_1$；
  • 进入中间状态 $q_1$，
    • 若当前值(输入值)为 1，则用 0 覆盖当前值，指针头不动，最后进入结束状态 $q_a$，退出；
    • 若当前值(输入值)为 0，则不变，指针头不动，最后进入结束状态 $q_a$，退出；

上面这个状态机要做的事情非常的简单，就是用我们定义的规则通过图灵机把 11、10 或者 01 变成了 00；可以用如下状态机进行表述，

实例

一进制加法

什么是一进制？1 表示 1，11 表示 2， 111 表示 3；那么自然 111+11=11111；这是最简单的加法运算；下面，我们是否可以输入一种规则，能够使得图灵机能够模拟人脑，实现任意多个 1 和另外任意多个 1 的加法？

假设，我们在纸带上输入公式，111+11=，如图，注意，B 表示 Blank 空格；

那么要如何使用图灵机完成该运算呢？我们定义如下图灵机规则，

1
2
3
4
5
6
7
8
9
10
11
q0,1,C,R,q1
q0,+,C,R,q0
q1,+,+,R,q1
q1,1,1,R,q1
q1,=,=,R,q1
q1,B,1,L,q2
q2,1,1,L,q2
q2,=,=,L,q2
q2,+,+,L,q2
q2,C,C,R,q0
q0,=,C,R,qa

表达式中，C表示 Clear，表示被指针头给擦除后的空格；任意多个 1 的加法的逻辑可以提炼成把左边的 5 个 1 依次移动到=符号的右边，然后将左边剩余的符号全部清除；把上述执行步骤的逻辑概括如下，

  1. 从起始位置开始，将 1 逐个移动到等号的右边，过程中清除+
  2. 最后清除=号
  3. 剩下的部分便是最终的结果

图灵机的计算过程，如下图所示，

上述的图灵规则可以放到图灵模拟器中去执行 https://landonwong.top/Tur/tur.html ，在规则表中写入规则，在表达式中写入 $111+11=$，然后点击设置，继续按钮即可执行；

上述一进制加法的图灵机对应的有限状态机，如下图所示，

二进制加法

规则如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
q0,1,1,R,q0
q0,0,0,R,q0
q0,K,K,L,qif
q0,+,+,L,qif（找到第一个未处理的加数位）
qif,1,K,R,q10
qif,0,K,R,q00（判断是0还是1）
q00,K,K,R,q00
q00,+,+,R,q00
q00,1,1,R,q00
q00,0,0,R,q00
q00,a,a,L,q01
q00,b,b,L,q01
q00,=,=,L,q01（找到第一个未处理的被加数位，并进入q01加0状态）
q01,1,b,L,qr
q01,0,a,L,qr
q01,K,a,L,qr
q01,+,a,L,qr（加0状态）
q10,+,+,R,q10
q10,1,1,R,q10
q10,0,0,R,q10
q10,a,a,L,q11
q10,b,b,L,q11
q10,=,=,L,q11
q10,K,K,R,q10（找到第一个未处理的被加数位，并进入q11加1状态）
q11,1,a,L,q12
q11,0,b,L,qr
q11,K,b,L,qr
q11,+,b,L,qr（加1状态）
q12,0,1,L,qr
q12,1,0,L,q12
q12,+,1,L,qr
q12,K,1,L,qr（进位状态）
qr,+,+,L,qr
qr,=,=,L,qr
qr,1,1,L,qr
qr,a,a,L,qr
qr,b,b,L,qr
qr,0,0,L,qr
qr,K,K,L,qr0
qr0,K,K,L,qr0
qr0,0,K,R,q00
qr0,1,K,R,q10
qr0,+,K,L,qr0
qr0,B,B,R,q3（倒退状态）
q3,+,+,R,q3
q3,a,K,R,q30
q3,b,K,R,q31
q3,=,K,L,qa
q3,K,K,R,q3
q3,0,K,R,q30
q3,1,K,R,q31
q31,a,a,R,q31
q31,b,b,R,q31
q31,=,=,R,q31
q31,1,1,R,q31
q31,0,0,R,q31
q31,B,1,L,qr
q30,a,a,R,q30
q30,b,b,R,q30
q30,=,=,R,q30
q30,1,1,R,q30
q30,0,0,R,q30
q30,B,0,L,qr（搬运状态）

注意如下规则，

  • K表示当前位已经被处理过，
  • a表示需要进入进位状态，比如 $1+1$，这个时候 $a=0$ 但是需要进入进位状态
  • 进位状态，不断左移，如果遇到 0 则加为 1，若遇到1，则改写为0，继续进位；

图灵机的计算过程如下，

可见，只要规则设置得当，图灵机完全可以帮助我们自动的去计算任意二进制数的加法；

总结

通过图灵规则和有限状态机，我们可以实现任意的可计数范围内的复杂计算；同样可以引申至乘除法；不过，这也能够让我们直观的体会到，即使是让图灵机自动的帮我们计算一个简单的二进制加法，所需要的规则也是非常复杂的！

感谢

很难找到通过图灵机实现加法的实现规则，因为一个简单的加法，规则也如此的复杂；这里非常感谢 LandonWong 的文章，https://blog.csdn.net/qq_16551309/article/details/88901940 ，文章中他详细的给出了如何实现加法的图灵规则和推演的详细过程；

意义

图灵机的伟大意义在于，它能够通过定义一套通用的规则，使得让机器可以自动的进行(可计数内的)任意复杂的计算；使得使用机器模拟人脑进行计算成为可能；为现代计算机奠定了理论基础；

不足

虽然图灵机可以自动完成任意复杂的运算，但是，它的不足之处是，

  1. 一系列定义的规则只适合一种数学运算，图灵机的规则复杂且使用范围单一；
  2. 没有保存运算中间结果；
  3. 完美的图灵机其实是实现不了的，因为我们无法提供无限长的纸带条；

能否将多种数学运算合二为一？能否存储中间结果？正是这两方面的原因，使得现代操作系统的概念呼之欲出！于是冯诺依曼提供了现代操作系统模型，

  1. 提供了中间结果存储器，通过中间结果，使得可以同时完成相互依赖的多种数学运算；(这里的一种数学运算就等价于现代计算机的一个计算指令)
  2. 并且将一种数学计算化简为一个计算机指令，比如一个加法指令(对比上述图灵机的加法，是不是简单了许多)，这样使得数学计算的设计更为简单；

Reference

图灵机论文: https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
wolfram’s price Turing: https://www.wolframscience.com/prizes/tm23/turingmachine.html
图灵机在线模拟器: https://landonwong.top/Tur/tur.html
剑桥大学: https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html
LandonWong 的博文: https://blog.csdn.net/qq_16551309/article/details/88901940