用 Rust 创建图灵机

引言

在本系列文章中，我将重写我在《在 Python 中创建图灵机》一文中编写的图灵机。我之所以重写它，是为了更熟悉 Rust 编程语言，并提高我的熟练度。

您可以在https://github.com/phillikus/rust_tm 上找到整个项目。

让我们首先回顾一下图灵机的基本理论，并在此基础上设置项目。

要求

• Rust 编程语言的基础知识
• 理论计算机科学基础

什么是图灵机？

图灵机是一种计算的数学模型，它根据规则表读取和写入磁带上的符号。每个图灵机都可以由一个状态列表和一个转移列表定义。基于起始状态 (s0)，图灵机在其所有状态之间进行处理，直到达到最终状态 (sf)。如果没有转移导致最终状态，图灵机将‘永远’运行并最终出错。

转移由当前状态、磁带当前位置的读取符号、下一个状态以及必须写入磁带的下一个符号定义。此外，它还包含一个方向，用于确定磁带头是应向左、向右移动还是不移动。为了可视化这个过程，让我们来看一个非常简单的图灵机，它将初始磁带上的值加一。

一元增量

为了简单起见，我们将从一元图灵机开始。一个“1”用“|”表示。因此，包含数字 3 的图灵机如下所示

$|||#

$ 表示我们图灵机的起始点，# 表示结束。增量完成后，我们期望最终的磁带看起来像这样

$||||#

为了达到这个最终状态，我们的图灵机只需读取所有“|”并附加一个“|”。

这可以用三个状态 s0、s1 和 sf 以及以下转移来表示

(s0, ‘$’, s1, ‘$’, Right)
(s1, ‘|’, s1, ‘|’, Right)
(s1, ‘#’, sf, ‘|’, Neutral)

这也可以用以下状态转移图来表示

 

我们从状态 s0 开始，期望读取“$”。然后我们切换到状态 s1 并写回“$”。然后，我们将磁带头向右移动一个字符。

在状态 s1 下，只要我们读取“|”，我们就会保持在状态 s1 并写回“|”。这样，我们将一直移动到磁带的右端。

最后，当我们遇到“#”时，我们写一个“|”并转到最终状态 sf。由于我们已经完成，此时没有理由移动磁带头。

项目结构

虽然这是一个非常简单的图灵机，但我们可以使用相同的模型来创建任何复杂度的机器。有了这些知识，我们现在就可以着手设计我们项目的基础结构了。为了表示整个图灵机，我们需要一个 struct 来表示状态、转移和磁带。

此外，我们需要一个枚举来表示我们可以移动图灵机磁带头的三个方向：左、右和无（不移动）。

最后，我们需要一个组件来组合所有这些组件并使用它们来处理图灵机。要设置项目，请打开命令行并输入

cargo new rust_tm

这应该会创建一个 Cargo.toml 文件以及一个包含 lib.rs 文件的 src/ 目录。删除此文件并为我们需要的每个 struct 添加一个文件，我最终得到了以下结构

现在我们可以直接开始编写代码了，让我们开始吧！

direction.rs

此文件包含将用于确定磁带头应移动方向的 enum。其实现非常直接

#[derive(Copy)]
pub enum Direction {
    Right,
    Left,
    None
}

impl Clone for Direction {
    fn clone(&self) -> Direction { *self }
}

正如您所见，我为 Clone trait 添加了一个实现。稍后您将看到为什么这是必需的。

tape.rs

我们将在 tape.rs 中定义的 tape struct 中使用此 enum

use direction;

pub struct Tape {
    pub alphabet: Vec<char>,
    pub head_position: i32,
    pub tape: Vec<char>
}

正如您所见，tape 由一个字母表组成，该字母表包含图灵机的所有有效字符，其磁带头位置用于知道它应该在哪里读取/写入下一个字符，以及磁带本身，它只是一个字符列表。

由于我们无法在 struct 本身中定义方法，因此我们将在其实现中添加它们

impl Tape {
    pub fn new(alphabet: &str, tape: &str) -> Tape {
        Tape { alphabet: alphabet.chars().collect(), head_position: 0, tape: tape.chars().collect() }
    }

    pub fn write(&mut self, character: char) {
        if !(self.head_position >= 1 && self.alphabet.contains(&character)) {
            return
        }

        self.tape[self.head_position as usize] = character;
    }

    pub fn read(&mut self) -> char {
        if self.head_position as usize > self.tape.len() {
            panic!("Trying to read character at invalid position: {}.", 
                    self.head_position.to_string());
        }

        self.tape[self.head_position as usize]
    }

    pub fn move_head(&mut self, direction: direction::Direction) {
        match direction {
            direction::Direction::Right => { self.head_position += 1; },
            direction::Direction::Left => { self.head_position -= 1; },
            direction::Direction::None => {}
        }
        
        if self.head_position < 0 {
            self.head_position = 0;
        }

        if self.head_position >= self.tape.len() as i32 {
            self.tape.push('#');
        }
    }

    pub fn to_string(&self) -> String {
        self.tape.iter().collect()
    }
}

让我们一步一步地进行

由于 Rust 本身不提供任何形式的构造函数，我们将在 new 方法中初始化 Tape，该方法将 word 和 alphabet 作为参数。为了使调用此方法变得简单，两个参数都接受一个 &str，然后将其转换为 Vec<char>。

此外，我们将 head_position 初始化为 0，表示磁带的起始位置。

write 和 read 方法简单地从磁带读取或写入一个字符。如果我们尝试在位置 0（磁带的起始位置）写入，或者我们尝试写入无效字符，代码将简单地返回以防止损坏状态。

当我们尝试读取超出磁带长度的位置时，代码将恐慌并显示异常消息。

move_head 方法接收一个 Direction 并将磁带头朝该方向移动。同样，我添加了一些边界检查，以防止磁带头超出磁带边界。

state.rs

此组件包含另一个 enum，它表示状态的类型，以及 State struct + 本身实现

#[derive(PartialEq)]
#[derive(Copy)]
pub enum StateType {
    Start,
    Empty,
    Final
}

#[derive(Copy)]
pub struct State {
    pub id: char,
    pub state_type: StateType
}

impl State {
    pub fn new(id: char, state_type: StateType) -> State {
        State { id, state_type }
    }
}

impl Clone for StateType {
    fn clone(&self) -> StateType { *self }
}

impl Clone for State {
    fn clone(&self) -> State { *self }
}

struct 本身只包含一个 id 和一个 state 类型，稍后将由图灵机进行评估。我们只需要以下状态：Start、Final 和 Empty。图灵机从 Start 状态开始，并在达到 Final 状态时结束。所有 Empty 状态都位于两者之间。

再次注意，我如何为 enum 和类实现 Clone trait（稍后详细介绍）。

transition.rs

同样，我们现在可以定义 Transition struct，它表示从图灵机的一个状态到下一个状态的流程。它包含当前状态和下一个状态，以及要写入磁带的当前字符和下一个字符

use state;
use direction;

#[derive(Copy)]
pub struct Transition {
    pub current_state: char,
    pub current_char: char,
    pub new_state: char,
    pub new_char: char,
    pub direction: direction::Direction
}

impl Transition {
    pub fn new(current_state: char, current_char: char, 
               new_state: char, new_char: char, direction: direction::Direction) -> Transition {
        Transition { current_state, current_char, new_state, new_char, direction }
    }
}

impl Clone for Transition {
    fn clone(&self) -> Transition { *self }
}

我们提供的唯一方法是 new，它允许我们快速创建新的转移。除此之外，此模块不包含任何逻辑。

tm.rs

一切就绪后，是时候看看 TM.rs 文件了。这就是所有繁重的工作所在

use tape;
use direction;
use transition;
use state;
use std;

pub struct TM {
    states: Vec<state::State>,
    transitions: Vec<transition::Transition>,
    pub tape: tape::Tape
} 

impl TM {
    pub fn new(states: Vec<state::State>, transitions: Vec<transition::Transition>, 
               tape: tape::Tape) -> TM {
        TM { states, transitions, tape }
    }

    pub fn process(&mut self, verbose: bool) { ... }
}

正如您所见，我们的 TM struct 由状态列表、转移列表和磁带组成。所有这些都将由 process 方法用于生成图灵机的最终输出，因此让我们更仔细地研究一下

pub fn process(&mut self) {
    let mut current_state: state::State = self.get_first_state();
    let mut step: i32 = 0;

    self.log_step(step);

    while current_state.state_type != state::StateType::Final {
        let current_char = self.tape.read();
        let state_id = current_state.id;

        let transition = *self.transitions.iter().clone()
        .find(|transition| transition.current_state == state_id && 
                           transition.current_char == current_char).unwrap();

        current_state = *self.states.iter().clone().find(|state| 
                         state.id == transition.new_state).unwrap();

        step += 1;
        self.tape.write(transition.new_char);
        self.tape.move_head(transition.direction);
        self.log_step(step);
    }
}

首先，我们初始化一个 current_state 变量并将其设置为图灵机的起始状态。为了获得第一个状态，我创建了以下辅助方法

fn get_first_state(&self) -> state::State {
    let mut iter = self.states.iter().cloned();
    let first_state: Option<state::State> = 
           iter.find(|state| state.state_type == state::StateType::Start);

    match first_state {
        None => panic!("No start state found."),
        Some(state) => state
    }
}

首先，我们获取一个可变迭代器并克隆它，以便我们可以在不遇到借用错误的情况下使用它。这也是为什么我们之前必须实现 Clone trait 的原因。然后我们尝试找到第一个 state_type == Start 的状态。

如果我们找到了一个 state，它将被返回，否则，我们的代码将恐慌并再次崩溃。

回到我们的 process 方法，我们初始化一个 step 变量来计算我们的图灵机到目前为止已执行的步数。然后，我们使用 log_step 方法记录此数字以及当前磁带

fn log_step(&mut self, step: i32) {
    println!("Tape after step {0}: {1} -> Head position: {2}", step, 
              self.tape.to_string(), self.tape.head_position);
}

在这里，我们只是以一种格式良好的方式打印磁带及其磁带头位置。

然而，所有的魔术都发生在 process 方法的 while 循环中

while current_state.state_type != state::StateType::Final {
    let current_char = self.tape.read();
    let state_id = current_state.id;

    let transition = *self.transitions.iter().clone()
     .find(|transition| transition.current_state == state_id && 
            transition.current_char == current_char).unwrap();
 
    current_state = *self.states.iter().clone().find
                    (|state| state.id == transition.new_state).unwrap();

   step += 1;
   self.tape.write(transition.new_char);
   self.tape.move_head(transition.direction);
   self.log_step(step);
}

根据 current_char 和 state_id，我们尝试找到第一个匹配的转移。

一旦我们有了转移，我们将尝试根据该转移的状态找到下一个 state。完成此操作后，我们只需增加图灵机运行的步数，将新字符写入磁带，并将磁带头移到相应的方向。

我们还调用 log_step 来将上一步的结果打印到控制台。

这就是我们将图灵机推到下一个状态所需要做的全部。此步骤将重复进行，直到图灵机达到 Final state。

测试图灵机

让我们通过测试我们的机器来可视化这个过程。为了简单起见，让我们从开头向您展示的 Increment 图灵机开始。要创建这样的机器，只需在 main.rs 中初始化并运行它

mod state;
mod tape;
mod direction;
mod transition;
mod tm;

fn main() {
    let mut tm : tm::TM = increment("$||#");
    tm.process(true);
}

fn increment(word: &str) -> tm::TM {
    let mut tape = tape::Tape::new("$|#", word);
    let states = vec![
        state::State::new('0', state::StateType::Start),
        state::State::new('1', state::StateType::Empty),
        state::State::new('f', state::StateType::Final)
    ];

    let transitions = vec![
        transition::Transition::new('0', '$', '1', '$', direction::Direction::Right),
        transition::Transition::new('1', '|', '1', '|', direction::Direction::Right),
        transition::Transition::new('1', '#', 'f', '|', direction::Direction::None)
    ];

    tm::TM::new(states, transitions, tape)
}

我将磁带初始化为值“||”，并将“|”作为唯一有效字符（除了 $ 和 #）。然后，我定义了状态和转移，并使用它们来实例化 TuringMachine。调用其 process 方法后，它应该通过所有这些状态和转移，并在磁带末尾写入最终的“|”。

如果我们到目前为止一切顺利，我们应该在控制台上看到以下输出

philipp@psrv1 ~/P/r/rust_tm> cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/rust_tm`
Tape after step 0: $||# -> Head position: 0
Tape after step 1: $||# -> Head position: 1
Tape after step 2: $||# -> Head position: 2
Tape after step 3: $||# -> Head position: 3
Tape after step 4: $||| -> Head position: 3

高级图灵机

现在我们的图灵机已经运行起来了，是时候添加一些更有趣的机器了。我们将坚持使用一元图灵机，并分别实现一个用于 Decrement、Addition 和 Subtraction 的机器

Decrement Machine

Decrement Machine 的工作方式与 Increment Machine 非常相似。但是，除了添加一个 | 之外，我们在到达磁带末尾后必须删除最后一个。这意味着我们必须一直向右移动，直到遇到第一个 # 字符。然后我们可以简单地向左移动一个字符并删除该 |

在 Rust 中，我们可以用以下代码表示这个图灵机

...
fn main() {
    let mut tm : tm::TM = decrement("$|||#");
    tm.process(true);
}

fn decrement(word: &str) -> tm::TM {
    let tape = tape::Tape::new("$|#", word);
    let states = vec![
        state::State::new('0', state::StateType::Start),
        state::State::new('1', state::StateType::Empty),
        state::State::new('2', state::StateType::Empty),
        state::State::new('f', state::StateType::Final)
    ];

    let transitions = vec![
        transition::Transition::new('0', '$', '1', '$', direction::Direction::Right),
        transition::Transition::new('1', '|', '1', '|', direction::Direction::Right),
        transition::Transition::new('1', '#', '2', '#', direction::Direction::Left),
        transition::Transition::new('2', '$', 'f', '$', direction::Direction::None),
        transition::Transition::new('2', '|', 'f', '#', direction::Direction::None)
    ];

    tm::TM::new(states, transitions, tape)
}

现在运行代码将产生以下结果

cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/rust_tm`
Tape after step 0: $|||# -> Head position: 0
Tape after step 1: $|||# -> Head position: 1
Tape after step 2: $|||# -> Head position: 2
Tape after step 3: $|||# -> Head position: 3
Tape after step 4: $|||# -> Head position: 4
Tape after step 5: $|||# -> Head position: 3
Tape after step 6: $||## -> Head position: 3

Addition Machine

我们可以创建的另一个简单的图灵机是加法机器。我们将用两个由 & 分隔的一元数字来表示加法运算。例如，要计算数字二和三的和，我们会这样初始化磁带：$||%|||。

为了添加这些数字，我们所要做的就是将 & 替换为 |，然后删除最后一个 |。对于上面的磁带，这将导致 $|||||。为了实现这一点，图灵机必须一直向右移动，直到遇到 %，将其替换为 |，然后继续向右移动，直到到达磁带末尾（由 # 标记）。最后，它必须向左移动一个字符并删除最后一个 |

这可以转化为以下 Rust 代码

...
fn main() {
    let mut tm : tm::TM = add("$|||#");
    tm.process(true);
}

fn add(word: &str) -> tm::TM {
    let tape = tape::Tape::new("$|&#", word);
    let states = vec![
        state::State::new('0', state::StateType::Start),
        state::State::new('1', state::StateType::Empty),
        state::State::new('2', state::StateType::Empty),
        state::State::new('3', state::StateType::Empty),
        state::State::new('4', state::StateType::Empty),
        state::State::new('f', state::StateType::Final)
    ];

    let transitions = vec![
        transition::Transition::new('0', '$', '1', '$', direction::Direction::Right),
        transition::Transition::new('1', '#', 'f', '#', direction::Direction::None),
        transition::Transition::new('1', '|', '1', '|', direction::Direction::Right),
        transition::Transition::new('1', '&', '2', '|', direction::Direction::Right),
        transition::Transition::new('2', '|', '2', '|', direction::Direction::Right),
        transition::Transition::new('2', '#', '3', '#', direction::Direction::Left),
        transition::Transition::new('3', '|', '4', '#', direction::Direction::Left),
        transition::Transition::new('4', '|', '4', '|', direction::Direction::Left),
        transition::Transition::new('4', '$', 'f', '$', direction::Direction::None)
    ];

    tm::TM::new(states, transitions, tape)
}

运行机器将产生以下结果

cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/rust_tm`
Tape after step 0: $|||&||# -> Head position: 0
Tape after step 1: $|||&||# -> Head position: 1
Tape after step 2: $|||&||# -> Head position: 2
Tape after step 3: $|||&||# -> Head position: 3
Tape after step 4: $|||&||# -> Head position: 4
Tape after step 5: $||||||# -> Head position: 5
Tape after step 6: $||||||# -> Head position: 6
Tape after step 7: $||||||# -> Head position: 7
Tape after step 8: $||||||# -> Head position: 6
Tape after step 9: $|||||## -> Head position: 5
Tape after step 10: $|||||## -> Head position: 4
Tape after step 11: $|||||## -> Head position: 3
Tape after step 12: $|||||## -> Head position: 2
Tape after step 13: $|||||## -> Head position: 1
Tape after step 14: $|||||## -> Head position: 0
Tape after step 15: $|||||## -> Head position: 0

Subtraction Machine

到目前为止，我们的图灵机一直相对简单。现在让我们来处理一个更复杂的问题：减法。解决这个问题的一种方法是遍历磁带，直到我们遇到第一个 #（我们将用它作为减号）。然后我们必须移除其右侧和左侧的下一个 |，并将它们替换为 #。

例如，给定磁带 $|||#||#，在这些第一步之后，磁带将如下所示：$||###|#。如果我们重复此过程，直到初始 # 的右侧没有更多 |，减法将完成。在这种情况下，我们将得到一个磁带，如：$|#####。

此过程适用于任何长度的磁带。但是，由于我们每一步都要遍历越来越多的 #，因此对于大型输入，图灵机将花费很长时间。

正如您在下面的图片中看到的，这个图灵机的图表比之前的图表复杂得多，需要一些时间才能完全理解它。

在 Rust 中，这由以下代码表示

fn main() {
    let mut tm : tm::TM = subtract("$|||#||");
    tm.process(true);
}

fn subtract(word: &str) -> tm::TM {
    let tape = tape::Tape::new("$|#", word);
    let states = vec![
        state::State::new('0', state::StateType::Start),
        state::State::new('1', state::StateType::Empty),
        state::State::new('2', state::StateType::Empty),
        state::State::new('3', state::StateType::Empty),
        state::State::new('4', state::StateType::Empty),
        state::State::new('5', state::StateType::Empty),
        state::State::new('6', state::StateType::Empty),
        state::State::new('7', state::StateType::Empty),
        state::State::new('8', state::StateType::Empty),
        state::State::new('f', state::StateType::Final)
    ];

    let transitions = vec![
        transition::Transition::new('0', '$', '0', '$', direction::Direction::Right),
        transition::Transition::new('0', '#', 'f', '#', direction::Direction::None),
        transition::Transition::new('0', '|', '1', '|', direction::Direction::Right),
        transition::Transition::new('1', '|', '1', '|', direction::Direction::Right),
        transition::Transition::new('1', '#', '2', '#', direction::Direction::Right),
        transition::Transition::new('2', '#', '2', '#', direction::Direction::Right),
        transition::Transition::new('2', '|', '3', '|', direction::Direction::Right),
        transition::Transition::new('3', '|', '4', '|', direction::Direction::Left),
        transition::Transition::new('3', '#', '6', '#', direction::Direction::Left),
        transition::Transition::new('4', '|', '5', '#', direction::Direction::Left),
        transition::Transition::new('5', '#', '5', '#', direction::Direction::Left),
        transition::Transition::new('5', '|', '2', '#', direction::Direction::Right),
        transition::Transition::new('5', '$', '2', '$', direction::Direction::Right),
        transition::Transition::new('6', '|', '7', '#', direction::Direction::Left),
        transition::Transition::new('7', '#', '7', '#', direction::Direction::Left),
        transition::Transition::new('7', '$', 'f', '$', direction::Direction::None),
        transition::Transition::new('7', '|', '8', '#', direction::Direction::Left),
        transition::Transition::new('8', '|', '8', '|', direction::Direction::Left),
        transition::Transition::new('8', '$', 'f', '$', direction::Direction::None)
    ];

    tm::TM::new(states, transitions, tape)
}

再次，运行我们的代码会产生正确的结果

cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/rust_tm`
Tape after step 0: $|||#|| -> Head position: 0
Tape after step 1: $|||#|| -> Head position: 1
Tape after step 2: $|||#|| -> Head position: 2
Tape after step 3: $|||#|| -> Head position: 3
Tape after step 4: $|||#|| -> Head position: 4
Tape after step 5: $|||#|| -> Head position: 5
Tape after step 6: $|||#|| -> Head position: 6
Tape after step 7: $|||#|| -> Head position: 5
Tape after step 8: $|||##| -> Head position: 4
Tape after step 9: $|||##| -> Head position: 3
Tape after step 10: $||###| -> Head position: 4
Tape after step 11: $||###| -> Head position: 5
Tape after step 12: $||###| -> Head position: 6
Tape after step 13: $||###|# -> Head position: 7
Tape after step 14: $||###|# -> Head position: 6
Tape after step 15: $||##### -> Head position: 5
Tape after step 16: $||##### -> Head position: 4
Tape after step 17: $||##### -> Head position: 3
Tape after step 18: $||##### -> Head position: 2
Tape after step 19: $|###### -> Head position: 1
Tape after step 20: $|###### -> Head position: 0
Tape after step 21: $|###### -> Head position: 0

这结束了我们的图灵机集合。我鼓励您尝试它们并创建新的。例如，您可以尝试实现乘法和除法图灵机。

希望您喜欢这篇文章。如果您有任何问题、困难或反馈，请在评论中告诉我。