目标

以简单的方式模拟图灵机。

用法

tm-interpreter<path-to-tm> [OPTIONS]
[OPTIONS]: -v -> 详细模式（逐步打印 TM 的步骤）

如何定义一个 TM

在文件中。例如

A Turing machine that accepts if the input is divisible by 3
alphabet: 0123456789
tape: 14526
tape_offset: 0
start_state: S0
accepted_states: S0
rule: S0 0369 none r S0
rule: S0 147 none r S1
rule: S0 258 none r S2
rule: S1 0369 none r S1
rule: S1 147 none r S2
rule: S1 258 none r S0
rule: S2 0369 none r S2
rule: S2 147 none r S0
rule: S2 258 none r S1

让我们来分析一下：基本结构是：keyword: <values>。任何不符合此格式的行都将被忽略。

字母表

设置要使用的字母表，这里所有可能的字符都是数字。

alphabet: 0123456789

带子

设置输入词。

tape: 14526

带子偏移量

定义带子开始的位置。偏移量为 3 将将带子向左移动 3 个字符（例如，如果您想在头部的左侧写入一个预言机，则偏移量将是该预言机的长度）

tape_offset: 0

状态

为了控制图灵机，使用状态模式。
在这里，我们不需要所有可能状态的不完整定义，因为起始状态和所有状态转换（我将它们称为规则）就足够了。
状态由其名称明确定义。

起始状态

图灵机开始的状态。

starting_state: S0

接受状态

定义哪些状态是接受结束状态。如果有多个，它们将用空格分隔，如下所示：S0 S1。

accepted_states: S0

规则（状态转换）

规则由 5 件事组成。

• 规则“活动”所在的状态
• 读取什么
• 写入什么
• 移动后
• 下一个状态

前两项是必须满足的条件，最后三项是在满足这些条件时采取的操作。一般而言：rule: <in-state> <read-condition> <write-action> <head_movement> <next-state>，其中
states 只是 String。
<read-condition> 以下之一

• any -> 如果磁带头部位置上写入任何字符
• empty -> 如果头部有字符
• 12345 -> 如果此包含头部字符（此规则将适用于[1-5]）

<write-action> 以下之一

• none -> 保持不变
• delete -> 删除当前字符
• a（单个字符）-> 写入 a

<movement> 是任何单个字符，l 向左移动，r 向右移动，其余保持不变。

rule: S1 258 none r S0
      ^^^^^^ if in state S1 and read 2, 5 or 8
             ^^^^^^^^^^ then leave the tape as is, move to the right and switch to state S0