Turing Machines

Are much powerful and general model of a computer

• Infinite tapes as unlimited memory
• Tape head reads and writes symbols and moves around on the tape
• Initially tape contains input string and is blank (ㄩ) everywhere else
• To read information machine has written on tape, moves head back over it
• Machine continues computing until it decides to produce an output
• The output accept and reject the input by entering designated accept and reject states. These are halting configurations
• The machine will go on running forever - never halting –if it never produces an output

这段内容介绍了 图灵机（Turing Machine, TM） 的概念，以及图灵机作为一种通用计算模型的工作方式。图灵机被认为是比有限状态机和下推自动机更强大、更通用的计算模型，具有 无限带（Infinite Tape） 作为 无限内存。

图灵机的组成部分：

1. 控制器（Controller）：
   • 图中的方块表示 控制器，它是图灵机的核心部分，负责控制机器的整体操作。
   • 控制器决定如何移动磁带头，如何根据读取的符号改变状态，并决定是否接受或拒绝输入。
2. 无限带（Infinite Tape）：
   • 无限带 可以视为 图灵机的内存，它可以在带上进行读写操作。
   • 这个带子是 无限长 的，具有无穷多的单元，初始时，带子上只有输入字符串，其他地方全部为空白（通常用符号 ㄩ 表示空符号）。
   • 磁带用来存储输入、输出和中间结果。
   • 在图中，带子包含了字符 a、b、c，两侧是空符号 ㄩ。
3. 磁带头（Tape Head）：
   • 磁带头 是图灵机的一个重要部分，负责读取和写入带子上的符号。
   • 磁带头可以在带上左右移动，从而访问带子的不同位置。
   • 在开始时，磁带头通常指向带上的第一个输入符号（图中的磁带头当前指向符号 a）。
   • 磁带头的移动 是图灵机操作的重要组成部分，它可以左移、右移或保持在当前位置。

图灵机的工作方式：

1. 读取和写入：
   • 磁带头从 带子上读取符号，并根据控制器的指令，可能在该位置上写入一个新的符号。
   • 读写的操作使得图灵机可以修改输入，从而进行更复杂的计算。
2. 无限内存的使用：
   • 无限带 使得图灵机具有 无限内存，这意味着它能够处理任意复杂度的计算问题，而不受内存大小的限制。
   • 在操作过程中，图灵机可以将中间计算结果写到磁带上，以便之后访问和使用。
3. 输入与输出：
   • 初始输入：带子上最初只包含输入字符串，其他部分都是空白符号 ㄩ。
   • 读取与写入：在计算过程中，图灵机通过移动磁带头来读取和写入带上的符号。
   • 当计算完成时，图灵机的控制器会进入 接受（accept） 或 拒绝（reject） 状态，表示接受或拒绝输入字符串。
   • 这些 接受和拒绝状态 被称为 停止配置（halting configuration），表示图灵机的计算过程结束。
4. 计算过程的停止与无限运行：
   • 图灵机在执行计算时，可以根据规则决定何时停止。
   • 当进入 接受状态 或 拒绝状态 时，图灵机会停止运行，这意味着计算过程完成并得出结果。
   • 但是，有些情况下图灵机可能 永不停止（never halting），也就是说，它会一直继续运行，而不会进入任何接受或拒绝状态。这种情况下，图灵机的行为是 无限循环，不能产生最终的输出。

图灵机的强大之处：

• 无限带 为图灵机提供了强大的计算能力，使它能够模拟任意形式的计算。
• 与有限自动机和下推自动机相比，图灵机可以解决更广泛的计算问题，因此被认为是 通用计算机模型 的基础。
• 图灵完备性（Turing Completeness）：图灵机能够模拟任何其他形式的计算（只要它们是有限可描述的），因此任何能够用图灵机计算的函数，都是 图灵可计算的。

总结：

• 图灵机（Turing Machine, TM） 是一种非常强大的计算模型，其核心由 控制器、无限带、磁带头 组成。
• 图灵机使用 无限带 作为内存，通过磁带头进行 读写操作 并左右移动，能够进行复杂的计算。
• 图灵机的 接受和拒绝状态 表示输入字符串是否被接受，而如果图灵机没有进入这些状态，它将 永远运行，无法得出结果。
• 图灵机 被认为是 通用计算模型，它的能力远超有限状态机和下推自动机，能够模拟几乎任何形式的计算。

Turing Machines

Imaginary machine

• Basic idea is to simulate the math computation process using the pen and the paper
• Write down or erase the symbols
• Move from one side to another
• Program and the input can be stored on tape, TM executes step by step till get the result which will be stored on tape

这段内容描述了 图灵机（Turing Machine, TM） 的概念，并通过 模拟数学计算过程 的方式来形象化理解图灵机的工作原理。图灵机可以被看作是一种 想象中的机器，其功能类似于人们在纸上进行数学运算的过程，通过简单的步骤逐步完成计算。

图灵机的基本概念和类比：

1. 模拟数学计算过程：
   • 图灵机的基本想法是通过 模拟数学计算的过程 来执行各种复杂的计算任务，类似于使用 笔和纸 进行数学运算。
   • 在这个过程中，图灵机就像一个在纸上操作的人，它不断写下符号、擦掉符号、并根据计算步骤移动到需要操作的地方。
2. 写入或擦除符号：
   • 写入符号：图灵机可以在磁带上 写下 需要的符号，就像在纸上记录中间步骤或结果。
   • 擦除符号：图灵机也可以 擦掉 不需要的符号，类似于在纸上修改或删除之前的内容。
   • 这种操作使得图灵机可以动态地修改计算过程中的数据，这与我们在纸上进行反复计算的行为类似。
3. 在磁带上移动：
   • 左右移动：图灵机通过 移动磁带头 来在磁带上读取和操作符号，就像人们在纸上从一侧移动到另一侧，查找之前写下的内容或在新的位置进行记录。
   • 这种左右移动使得图灵机可以访问磁带上的任意位置，并根据计算的需要进行操作。
4. 程序和输入存储在磁带上：
   • 输入和程序都存储在磁带上：在图灵机的模型中，输入数据 和 程序的指令 都可以存储在磁带上。
   • 图灵机会逐步读取这些内容，并根据程序的指令对输入进行处理。
   • 逐步执行程序：图灵机会按照程序的步骤逐步执行每一项操作，直到得到计算的结果。
   • 结果存储在磁带上：计算的 结果 也会被存储在磁带上，类似于在纸上记录计算的最终答案。

类比理解图灵机的工作原理：

• 像在纸上计算：图灵机的操作类似于人们在纸上计算数学问题。它有一个 "笔"（磁带头）来记录和修改数据，有一个 "纸"（磁带）作为无限的存储空间，并且有一个控制逻辑（类似于人们的思维过程）来决定接下来的步骤。
• 一步一步地计算：每次操作都是 有序的、逐步的，就像一个人按照数学计算步骤一步一步来完成问题，直到得到结果。

总结：

• 图灵机 是一种模拟数学运算过程的 想象中的机器，它可以使用类似于笔和纸的方式来完成各种计算任务。
• 写入、擦除和移动：图灵机可以在磁带上 写入或擦除符号，并且可以 在磁带上左右移动，以便进行下一步的操作。
• 输入和程序存储在磁带上，图灵机会逐步读取并执行程序，直到计算出结果。
• 这种 逐步执行、写入、擦除和移动 的操作，使得图灵机能够执行复杂的计算任务，是一种通用的计算模型。

Turing Machines