图灵机

图灵机（Turing machine）是图灵提出的一种抽象计算模型，它主要包括一个无限长的纸带（tape）、一个读写头（head）以及一系列状态和指令规则：

  • 纸带（tape）：图灵机的纸带被划分为单元格，每个单元格上可以存储一个字符。纸带是无限长的，可以向左或向右无限延伸。
  • 字符表（alphabet）：即字符的集合，它包含纸带上可能出现的所有字符。其中包含一个特殊的空白字符（blank），意思是此格子没有任何字符，这是默认状态。
  • 读写头（head）：读写头是指向纸带上的一个单元格的指针，可以读取/擦除/写入当前单元格的内容，也可以根据移动到相邻的单元格。
  • 指令集（instructions table）：包括一组有限长度的指令，它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
  • 状态寄存器（state register）：它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。

图灵机可以接受一些输入并产生输出，并根据状态转换规则进行计算。这个模型的关键在于它的简洁性和能力，因为图灵机可以模拟任何其他的计算设备，通过状态转换规则，它可以模拟现代计算机的运算过程。虽然图灵机是一个抽象的概念，但它对计算理论和计算机科学产生了深远的影响，尤其是对于计算可计算性和算法可解性的研究。

Brainfuck语言

Brainfuck语言是一个极小化的图灵完全的编程语言，由Urban Müller在1993年创造，与图灵机的抽象概念非常契合。 BF语言作为图灵机的示例，展示了计算理论中的重要概念，并证明了一种简单语言也能表达通用的计算， 但是由于语言本身非常简单，程序代码的可读性非常差。

Brainfuck语言模型主要包括：

  • 内存模拟：
    • 一个可以读写的以字节为单位、已初始化为零的数组，模拟程序内存（相当于图灵机的纸带）
    • 一个指向该内存数组的内存指针，指向当前操作的内存位置，开始时指向数组的第一个字节（相当于图灵机的读写头）
  • 指令模拟：（相当于图灵机的指令集）
    • 八种基本指令，分别由一个字符标识，对应的八个字符就是Brainfuck源码的全部合法字符
    • 一个只读的基本指令序列，模拟程序源码
    • 一个程序计数器（Program Counter，PC），用于存储下一条将要执行的指令的地址
  • 用于输入输出缓冲的两个字节流

下面是这八种基本指令的描述，每个指令由一个字符标识：

  1. >：内存指针后移
  2. <：内存指针前移
  3. +：内存指针所指字节的值加一
  4. -：内存指针所指字节的值减一
  5. .：将内存指针当前指向的字节内容，传递给输出流
  6. ,：从输入流获取一个字节的内容，写入内存指针当前指向的位置
  7. [：若内存指针所指字节的值为零，则pc向后跳转到其对应的]的下一个指令处，否则无效果
  8. ]：若内存指针所指字节的值不为零，则pc向前跳转到其对应的[的下一个指令处，否则无效果

除了两个特殊的跳转指令，在其它指令执行后，pc都会自动加一，并顺序执行下一条指令，直到程序结束。

Python实现

Brainfuck语言的解释器的实现非常简洁，除了循环需要使用一个栈之外，其它的操作都是直接的。

Python实现的Brainfuck解释器和基本用例如下，注意到这里并没有对接标准输入输出流，而是需要提供一个固定的字符串作为输入流，并且将程序的所有输出保存在字符串中返回。 

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
64
65
66
67
68
69
class BrainfuckInterpreter:
    def __init__(self):
        self.memory = [0] * 1000
        self.pointer = 0
        self.loop_stack = []
        self.input_buffer = ""
        self.output_buffer = ""

    def input(self):
        if len(self.input_buffer) > 0:
            a = ord(self.input_buffer[0])
            self.input_buffer = self.input_buffer[1:]
            return a
        else:
            raise RuntimeError("input was required")

    def output(self, a):
        self.output_buffer += chr(a)

    def interpret(self, code):
        pc = 0
        while pc < len(code):
            command = code[pc]

            if command == ">":
                self.pointer += 1
            elif command == "<":
                self.pointer -= 1
            elif command == "+":
                self.memory[self.pointer] += 1
            elif command == "-":
                self.memory[self.pointer] -= 1
            elif command == ".":
                self.output(self.memory[self.pointer])
            elif command == ",":
                self.memory[self.pointer] = self.input()
            elif command == "[":
                if self.memory[self.pointer] == 0:
                    loop_nest = 1
                    while loop_nest != 0:
                        pc += 1
                        if code[pc] == "[":
                            loop_nest += 1
                        elif code[pc] == "]":
                            loop_nest -= 1
                else:
                    self.loop_stack.append(pc)
            elif command == "]":
                if self.memory[self.pointer] != 0:
                    pc = self.loop_stack[-1]
                else:
                    self.loop_stack.pop()
            else:
                raise RuntimeError("invalid character")

            pc += 1

    def run(self, code, input_str=""):
        self.input_buffer = input_str
        self.interpret(code)
        return self.output_buffer


if __name__ == "__main__":
    bf_code = "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.\
        +++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>."
    interpreter = BrainfuckInterpreter()
    result = interpreter.run(bf_code)
    print(result)

这里的源码是输出Hello World!