创建 Python 图灵机 - 第 2 部分

在上一部分中，我们介绍了图灵机的理论，并创建了基本的项目结构和类。现在我们将逐一实现这些类。

direction.py

此类仅包含一个 enum，用于移动磁带的读写头。因此，其实现非常直接。

from enum import Enum

class Direction(Enum):
    Left = 1
    Right = 2
    Neutral = 3

我们将在 tape.py 类中使用此 enum，因此我们直接开始。

tape.py

from direction import Direction

class Tape:
    def __init__(self, word, alphabet):
        self.alphabet = alphabet + "$#"        
        self.head_position = 0
        self.__init_tape(word)

    def __init_tape(self, word):
        tape = "$";
        for char in (c for c in word if c in self.alphabet):
            tape += char
        tape += "#";
        self._tape = list(tape)

    def write(self, character):
        if self.head_position < 1 or character not in self.alphabet:
            return
        self._tape[self.head_position] = character

        last_item_index = len(self._tape) - 1
        if self.head_position == last_item_index:
            self._tape += '#'

    def read(self):
        if self.head_position < 0 or self.head_position > len(self._tape) - 1:
            raise Exception('Trying to read character at invalid position: ' + self.head_position)
        return self._tape[self.head_position]

    def get_tape(self):
        self._remove_trailing_sharps()
        return ''.join(self._tape)

    def move_head(self, direction):
        if direction == Direction.Right:
            self.head_position += 1
        elif direction == Direction.Left:
            self.head_position -= 1

        if self.head_position > len(self._tape) - 1:
            self._tape += '#'
        if self.head_position < 0:
            self.head_position = 0

    def get_length(self):
        return len(self._tape)

    def _remove_trailing_sharps(self):
        for i in range(len(self._tape) - 1, 1, -1):
            if self._tape[i] == '#' and self._tape[i-1] == '#':
                del self._tape[-1:]
            else:
                break

我们逐一进行讲解。

__init__ 方法接收一个 word 和一个 alphabet。首先，我们将 $ 和 # 字符添加到字母表中，因为它们分别代表磁带的起始和结束字符。然后，我们初始化一个 head_position 成员变量，并将其设置为 0，即磁带的起始位置。最后，我们调用 __init_tape 方法，该方法会将 word 中的所有字符（只要它们在字母表中）放入磁带。最后，它将磁带转换为一个列表。
我分别用双下划线和单下划线标记了 __init_tape 和 _tape，以将它们标记为受保护，并防止消费者使用它们。

write 和 read 方法仅从磁带读取或向磁带写入字符。请注意，当我们在磁带末尾写入 char 时，我们添加了一个额外的 #。这使我们可以根据需要增加磁带的大小。
接下来，我们有 get_tape 和 _remove_trailing_sharps 方法，它们将用于返回磁带的当前状态。
最后，move_head 方法接收一个 Direction 并将磁带读写头朝该方向移动。

state.py

此组件包含另一个 enum，它代表状态的类型以及 State 类本身。

from enum import Enum

class StateType(Enum):
    Start = 1
    Final = 2
    Empty = 3

class State:
    def __init__(self, id, state_type):
        self.id = id
        self.type = state_type

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

transition.py

同样，我们现在可以定义 Transition 类。它包含当前状态和下一个状态，以及要写入磁带的当前字符和下一个字符。

from state import State

class Transition:
    def __init__(self, current_state, current_char, new_state, new_char, direction):
        self.current_state = current_state
        self.current_char = current_char
        self.new_state = new_state
        self.new_char = new_char
        self.direction = direction

设置好所有基本类后，我们现在可以开始实现图灵机了。

turing_machine.py

此类结合了我们之前定义的所有类，并使用它们在图灵机的状态之间移动，直到达到最终状态。

from state import StateType

class TuringMachine:
    def __init__(self, states, transitions, tape):
        self.states = states
        self.start_state = self.get_start_state()
        self.transitions = transitions
        self.tape = tape

    def get_tape(self):
        return self.tape.get_tape()

    def get_start_state(self):
        return next(state for state in self.states if state.type == StateType.Start)

    def process(self, verbose=False):
        current_state = self.start_state

        while current_state.type != StateType.Final:
            current_char = self.tape.read()
            state_id = current_state.id

            transition = next(t for t in self.transitions
                              if t.current_state == state_id
                              and t.current_char == current_char)

            current_state = next(state for state in self.states if state.id == transition.new_state)

            self.tape.write(transition.new_char)
            self.tape.move_head(transition.direction)

__init__ 方法接收状态列表、转换列表和磁带。
让我们仔细看看 process 方法，其中包含图灵机的主要逻辑。

current_state = self.start_state

首先，我们初始化一个 current_state 变量，并将其设置为图灵机的起始状态。在每次迭代中，我们将尝试查找图灵机的下一个状态并将其分配给此变量。当达到最终状态时，process 方法就完成了。

while current_state.type != StateType.Final:
   current_char = self.tape.read()
   state_id = current_state.id

在此循环中，我们首先从磁带和当前状态获取当前字符和 state-id。然后，我们同时使用它们来查找与这些值匹配的第一个转换。

transition = next(t for t in self.transitions if t.current_state == state_id and t.current_char == current_char)

由于此转换包含图灵机的下一个状态，因此我们将使用它来覆盖 current_state 变量。

current_state = next(state for state in self.states if state.id == transition.new_state)

最后，我们必须将转换中的新字符写入磁带，并按照转换定义的 Direction 移动磁带。

self.tape.write(transition.new_char)
self.tape.move_head(transition.direction)

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

测试图灵机

由于整个过程可能有点抽象，让我们通过测试我们的机器来尝试将其可视化。为了简单起见，我决定从上一部分中向您展示的 Increment 图灵机开始。要创建这样的机器，我添加了一个新文件 console_client.py 并将以下代码放入其中。

from turing_machine import TuringMachine
from state import State, StateType
from transition import Transition
from direction import Direction
from tape import Tape

tape = Tape('|||', '|')
states = [
            State("s0", StateType.Start),
            State("s1", StateType.Empty),
            State("sf", StateType.Final)
         ]

transitions = [
                 Transition("s0", "$", "s1", "$", Direction.Right),
                 Transition("s1", "|", "s1", "|", Direction.Right),
                 Transition("s1", "#", "sf", "|", Direction.Neutral)
              ]

tm = TuringMachine(states, transitions, tape)
tm.process();
print(tm.get_tape())

要跟上图灵机的定义，请返回第 1 部分。
我用值 ‘|||’ 初始化了磁带，并将 ‘|’ 作为唯一有效字符（除了 $ 和 #）。然后我定义了状态和转换，并使用它们来实例化 TuringMachine。调用其 process 方法应该会遍历所有这些状态和转换，并在磁带末尾写入一个最终的 ‘|’。
如果我们一切都做对了，最后的打印语句应该显示：$||||#。

第 2 部分就到这里！希望您喜欢这篇文章。在最后一部分中，我们将添加一些更复杂的图灵机，并扩展日志记录功能，这将使我们能够看到图灵机执行的每一步的结果。
感谢您阅读本文。 :) 如果您有任何问题、困难或反馈，请在评论中告知我。