【计算机基础理论】图灵机（Turing Machine）
Alan Turing: 《On Computable Numbers, with an Application to the Entscheidungsproblem》
resource: https://people.math.ethz.ch/~halorenz/4students/Literatur/TuringFullText.pdf
文章背景：这篇论文是图灵为了回答大卫·希尔伯特（David Hilbert）提出的“判定问题”（Entscheidungsproblem）而写的。判定问题是指：“是否存在一个通用的方法或算法，可以判断任何一个数学命题是否为真或假”。图灵通过图灵机这个抽象计算模型，证明了并不存在这样一个通用的算法，解决了希尔伯特的判定问题。
1 定义
图灵机（Turing Machine）是一种数学模型，由英国数学家艾伦·图灵于1936年提出，用来描述计算过程的理论机器。它是计算理论中的一个基本概念，定义了“算法”和“计算”是什么，能够模拟任何实际计算机的计算任务。
1.1 图灵机的构成部分
图灵机是一个抽象的计算模型，用来模拟任何可计算的过程。其主要构成部分包括：
- 纸带（Tape）：图灵机的纸带是无限长的，分为许多方格，每个方格可以写入一个符号（例如0或1）。纸带相当于图灵机的内存，用于存储输入、输出以及中间计算的结果。
- 读写头（Head）：图灵机的读写头可以在纸带上左右移动。它可以读取当前所在方格的符号，并根据当前状态和读到的符号决定下一步操作，如写入新的符号或移动方向。
- 状态集合（m-configurations）：图灵机有一个有限的状态集，每个状态控制着机器的行为。图灵机的行为完全由当前的状态和读取到的符号决定。
- 状态转移函数（State Transition Function）：这是一个规则集，规定了在每种状态和符号下图灵机应该如何操作。图灵机会在不同状态间切换，并通过读写头修改纸带上的符号。
1.2 利用图灵机的案例
论文中的一个简单实例演示了图灵机如何计算二进制序列。以下是一个图灵机用于计算交替的0和1的序列的案例。
图灵机的操作表如下：
- 初始状态
b，纸带为空白，图灵机开始在纸带上写入0，并移动读写头到下一格。 - 进入状态
r，然后在下一格写入1，继续向右移动读写头。 - 不断重复，交替写入
0和1，从而生成序列010101...。
每次操作的规则为：
- 如果当前状态为
b并且读到空白，则写入0并进入状态r。 - 如果当前状态为
r并且读到空白，则写入1并返回状态b。
通过这种方式，图灵机可以无限地生成交替的二进制序列。
2 文章说明
本文内容来自大模型生成内容，笔者意在记录学习过程，最大的愿望是希望有理解更深层次的学者能够指导，说明这篇生成内容是否正确，并讲讲自己对图灵机的理解，不胜感激！