图灵完备（Turing completeness）

在可计算性理论中，如果一个数据操作规则系统（如计算机的指令集、编程语言或细胞自动机）可以用来模拟任何图灵机器（由英国数学家和计算机科学家阿兰·图灵（Alan Turing）设计），则称其为图灵完备（Turing-complete）或计算通用的。

图灵等价（Turing equivalence）

若P可以模拟Q，Q可以模拟P，那个么这两个数据操作规则系统P和Q就是图灵等价的。

图灵机（Turing machine）

图灵机（Turing Machine）是图灵在1936年发表的 《论可计算数及其在判定性问题上的应用》（《On Computable Numbers, with an Application to the Entscheidungsproblem》）中提出的数学模型。

图灵机的结构包括以下几个部分：

  • 一条无限长的纸带（tape），纸带被分成一个个相邻的格子（square），每个格子都可以写上至多一个字符（symbol）。
  • 一个字符表（alphabet），即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符。
  • 一个读写头（head），可理解为指向其中一个格子的指针。它可以读取/擦除/写入当前格子的内容，此外也可以每次向左/右移动一个格子。
  • 一个状态寄存器（state register），它追踪着每一步运算过程中，整个机器所处的状态（运行/终止）。当这个状态从运行变为终止，则运算结束，机器停机并交回控制权。如果你了解有限状态机，它便对应着有限状态机里的状态。
  • 一个有限的指令集（instructions table），它记录着读写头在特定情况下应该执行的行为。可以想象读写头随身有一本操作指南，里面记录着很多条类似于“当你身处编号53的格子并看到其内容为0时，擦除，改写为1，并向右移一格。此外，令下一状态为运行。”这样的命令。其实某种意义上，这个指令集就对应着程序员所写下的程序了。

turing_machine_inner

在计算开始前，纸带可以是完全空白，也可以在某些格子里预先就有写上部分字符作为输入。运算开始时，读写头从某一位置开始，严格按照此刻的配置（configuration），即：

  • 当前所处位置
  • 当前格子内容

来一步步的对照着指令集去进行操作，直到状态变为停止，运算结束。而后纸带上留下的信息，即字符的序列（比如类似“…011001…”）便作为输出，由人来解码为自然语言。

停机问题（Halting Problem）

在可计算性理论中，停机问题是根据对任意计算机程序和输入的描述，确定程序是否将完成运行，还是将永远继续运行的问题。阿兰·图灵在1936年证明，解决所有可能的程序输入对的停机问题的通用算法不存在。

自动机（Automation）

自动机是有限状态自动机（Finite State Machine，FSM）的数学模型。有限状态自动机是给定符号输入，依据（可表达为一个表格的）转移函数“跳转”过一系列状态的一种机器。

  1. 有限状态自动机（Finite Automata，FA）
    1. 确定有限自动机（Deterministic Finite Automata，DFA）
      自动机的每个状态都有对字母表中所有符号的转移。
    2. 非确定有限自动机（Non-deterministic Finite Automata，NFA）
      自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。
      上述自动机接受的语言家族被称为正规表达式(Regular Expression)
  2. 下推自动机（Pushdown Automation，PDA）
    下推自动机额外的装备了栈形式的内存。下推自动机是一种实现上下文无关语法的方式。
  3. 线性有界自动机（Linear Bounded Automation，LBA）
    线性有界自动机是有限制的 图灵机；不使用无限磁带，它的磁带有同输入字元串成正比的空间。线性有界自动机接受上下文有关语言。
  4. 图灵机（Turing Machine）
    图灵机是最强力的自动机。图灵机拥有磁带形式的无限内存，和可以读取和变更磁带的磁头，它可在磁带上向任何方向移动。图灵机等价于演算法，可以用来判定递归语言并识别递归可枚举语言。

Brainfuck 语言

在1993年，Urban Müller 发明了 Brainfuck 语言。这门语言可以说是编程语言界的 helloworld 了——它一共只含有 8 个有效字符，每个有效字符就是一条指令。语言虽然极致轻量，它却是一门图灵完备的编程语言。

语言里的 8 个有效字符分别是：

  • >
    指针向右移动一格
  • <
    指针向左移动一格
  • +
    使指针当前格数值加一
  • -
    使指针当前格数值减一
  • .
    把当前格数值按 ASCII 表输出到终端
  • ,
    从终端接受 1 byte 的数据，存储其 ASCII 数值到当前格
  • [
    当指针当前值为 0 时，程序跳转至与之对应的 ] 之后；否则程序正常执行
  • ]
    程序跳转回与之对应的 [ 处

brainfuck-visualizer 提供了 Brainfuck 的可视化解析过程。

Brainfuck 的 8 个指令可以等价的转换为 C/C++ 语言语法：

Brainfuck C
> ++ptr;
< --ptr;
+ ++*ptr;
- --*ptr;
. putchar(*ptr);
, *ptr=getch();
[ while(*ptr){
] }
Windows
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
string translate(char c) {
    switch(c) {
        case '>':
            return "p++";
        case '<':
            return "p--";
        case '+':
            return "*p = *p + 1";
        case '-':
            return "*p = *p - 1";
        case '.':
            return "cout << char(*p)";
        case ',':
            return "*p = getchar()";
        case '[':
            return "while(*p) {";
        case ']':
            return "}";
        default:
            return "";
    }
}
void run() {
    char arr[1000] = { 0 };
    char* p = arr + 500;
}
int main() {
    run();
    freopen("D:/out.text", "w", stdout);
    char c;
    while(cin >> c) {
        cout << translate(c);
        if (c != '[')
            cout << ";\n";
    }
    return 0;
}