量子計算学習ノート - チューリング機械5

bbrfkr

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。

この記事では、これまで机上で議論を続けてきたチューリング機械をpythonで実際に実装してみて、その動きを確かめることにする。実際のソースコードはこちらに格納してある。

肝となる実装は「SingleTapeTuringMachine」クラスである。これは単一の無限長テープを持つチューリング機械を模して実装したクラスだ。

class SingleTapeTuringMachine:
    is_valid = False

    class Index(Enum):
        NOW_STATE = 0
        READ_ALPHABET = 1
        NEXT_STATE = 2
        WRITTEN_ALPHABET = 3
        DIRECTION_HEAD = 4

    def __init__(
        self,
        tape: str,
        alphabets: list[str],
        states: list[str],
        initial_state: str,
        halt_state: str,
        program: list[tuple[str, str, str, str, int]],
    ):
        self.tape = tape
        self.alphabets = alphabets
        self.states = states
        self.initial_state = initial_state
        self.halt_state = halt_state
        self.program = program

    def validate(self):
        if not check_alphabets(alphabets=self.alphabets):
            raise ValidationError("alphabets list is not valid.")
        if not check_tape(tape=self.tape, alphabets=self.alphabets):
            raise ValidationError("tape is not valid.")
        if not check_states(
            states=self.states,
            initial_state=self.initial_state,
            halt_state=self.halt_state,
        ):
            raise ValidationError("states list is not valid.")
        if not self._check_program():
            raise ValidationError("program is not valid.")
        self.is_valid = True

    def execute(self):
        if not self.is_valid:
            raise ValidationError("validation is not executed.")
        step = 0
        state = self.initial_state
        head = 0
        while state != self.halt_state:
            print(f"===== step {step} =====")
            self.print_tape_and_head(head)
            alphabet = self.tape[head]
            for row in self.program:
                if (
                    row[self.Index.READ_ALPHABET.value] == alphabet
                    and row[self.Index.NOW_STATE.value] == state
                ):
                    self.tape = (
                        self.tape[:head]
                        + row[self.Index.WRITTEN_ALPHABET.value]
                        + self.tape[head + 1 :]
                    )
                    state = row[self.Index.NEXT_STATE.value]
                    if head != 0 or row[self.Index.DIRECTION_HEAD.value] != -1:
                        head = head + row[self.Index.DIRECTION_HEAD.value]
                    step = step + 1
                    break
                # programを全走査しても対象行がない場合はエラー
                if row == self.program[-1]:
                    print(f"execution error!")
                    return False
        print(f"===== step final =====")
        self.print_tape_and_head(head)
        return True

要所要所を解説しよう。

    class Index(Enum):
        NOW_STATE = 0
        READ_ALPHABET = 1
        NEXT_STATE = 2
        WRITTEN_ALPHABET = 3
        DIRECTION_HEAD = 4

「Index」Enumクラスは、Program行の各列が何を表しているかをわかりやすくするためのクラス。これにより以下のようにプログラムは扱われることになる。

  • 0番目: 現在の状態 (NOW_STATE)

  • 1番目: ヘッドに読み取られたアルファベット (READ_ALPHABET)

  • 2番目: 次に遷移する状態 (NEXT_STATE)

  • 3番目: ヘッドに書き込まれるアルファベット (WRITTEN_ALPHABET)

  • 4番目: ヘッドの動く方向 (DIRECTION_HEAD)

「SingleTapeTuringMachine」クラスではまずチューリング機械として定義が妥当か、「validate」メソッドを実行してからプログラムの実行を行うようにした。このため「validate」メソッドでは、アルファベットとテープに書かれた内容に整合性があるか、状態とプログラム間にも整合性があるかをチェックして、問題なければ「is_valid」フラグを立てるようにする。

    def validate(self):
        if not check_alphabets(alphabets=self.alphabets):
            raise ValidationError("alphabets list is not valid.")
        if not check_tape(tape=self.tape, alphabets=self.alphabets):
            raise ValidationError("tape is not valid.")
        if not check_states(
            states=self.states,
            initial_state=self.initial_state,
            halt_state=self.halt_state,
        ):
            raise ValidationError("states list is not valid.")
        if not self._check_program():
            raise ValidationError("program is not valid.")
        self.is_valid = True

「is_valid」フラグが「True」であればプログラムは少なくとも実行できるので、「execute」メソッドで実行することができる。プログラムのデバッグに役立つよう、現在が何ステップ目の遷移後かを出力するようにしている。

    def execute(self):
        if not self.is_valid:
            raise ValidationError("validation is not executed.")
        step = 0
        state = self.initial_state
        head = 0
        while state != self.halt_state:
            print(f"===== step {step} =====")
            self.print_tape_and_head(head)
            alphabet = self.tape[head]
            for row in self.program:
                if (
                    row[self.Index.READ_ALPHABET.value] == alphabet
                    and row[self.Index.NOW_STATE.value] == state
                ):
                    self.tape = (
                        self.tape[:head]
                        + row[self.Index.WRITTEN_ALPHABET.value]
                        + self.tape[head + 1 :]
                    )
                    state = row[self.Index.NEXT_STATE.value]
                    if head != 0 or row[self.Index.DIRECTION_HEAD.value] != -1:
                        head = head + row[self.Index.DIRECTION_HEAD.value]
                    step = step + 1
                    break
                # programを全走査しても対象行がない場合はエラー
                if row == self.program[-1]:
                    print(f"execution error!")
                    return False
        print(f"===== step final =====")
        self.print_tape_and_head(head)
        return True

さて、「SingleTapeTuringMachine」クラスを用いて、常に1を出力する関数「$${f(x) = 1}$$」は次のようにプログラミングされる。

from lib.turing_machines import SingleTapeTuringMachine

tm = SingleTapeTuringMachine(
    tape=">10110--",
    alphabets=[">", "1", "0", "-"],
    states=["qi", "q1", "q2", "q3", "qh"],
    initial_state="qi",
    halt_state="qh",
    program=[
        ("qi", ">", "q1", ">", 1),
        ("q1", "0", "q1", "-", 1),
        ("q1", "1", "q1", "-", 1),
        ("q1", "-", "q2", "-", -1),
        ("q2", "-", "q2", "-", -1),
        ("q2", ">", "q3", ">", 1),
        ("q3", "-", "qh", "1", 0),
    ],
)

tm.validate()
tm.execute()

これを実行すると次のようになる。

===== step 0 =====
>10110--
↑
===== step 1 =====
>10110--
 ↑
===== step 2 =====
>-0110--
  ↑
===== step 3 =====
>--110--
   ↑
===== step 4 =====
>---10--
    ↑
===== step 5 =====
>----0--
     ↑
===== step 6 =====
>-------
      ↑
===== step 7 =====
>-------
     ↑
===== step 8 =====
>-------
    ↑
===== step 9 =====
>-------
   ↑
===== step 10 =====
>-------
  ↑
===== step 11 =====
>-------
 ↑
===== step 12 =====
>-------
↑
===== step 13 =====
>-------
 ↑
===== step final =====
>1------
 ↑

同じように、ビット列の各々のビットを反転する関数は次のようにプログラミングできる。

from lib.turing_machines import SingleTapeTuringMachine

tm = SingleTapeTuringMachine(
    tape=">1101101010-",
    alphabets=[">", "1", "0", "-"],
    states=["qi", "q1", "q2", "qh"],
    initial_state="qi",
    halt_state="qh",
    program=[
        ("qi", ">", "q1", ">", 1),
        ("q1", "0", "q1", "0", 1),
        ("q1", "1", "q1", "1", 1),
        ("q1", "-", "q2", "-", -1),
        ("q2", "0", "q2", "1", -1),
        ("q2", "1", "q2", "0", -1),
        ("q2", ">", "qh", ">", 1),
    ],
)

tm.validate()
tm.execute()

これの実行結果はこうなる。

===== step 0 =====
>1101101010-
↑
===== step 1 =====
>1101101010-
 ↑
===== step 2 =====
>1101101010-
  ↑
===== step 3 =====
>1101101010-
   ↑
===== step 4 =====
>1101101010-
    ↑
===== step 5 =====
>1101101010-
     ↑
===== step 6 =====
>1101101010-
      ↑
===== step 7 =====
>1101101010-
       ↑
===== step 8 =====
>1101101010-
        ↑
===== step 9 =====
>1101101010-
         ↑
===== step 10 =====
>1101101010-
          ↑
===== step 11 =====
>1101101010-
           ↑
===== step 12 =====
>1101101010-
          ↑
===== step 13 =====
>1101101011-
         ↑
===== step 14 =====
>1101101001-
        ↑
===== step 15 =====
>1101101101-
       ↑
===== step 16 =====
>1101100101-
      ↑
===== step 17 =====
>1101110101-
     ↑
===== step 18 =====
>1101010101-
    ↑
===== step 19 =====
>1100010101-
   ↑
===== step 20 =====
>1110010101-
  ↑
===== step 21 =====
>1010010101-
 ↑
===== step 22 =====
>0010010101-
↑
===== step final =====
>0010010101-
 ↑

この記事が気に入ったらサポートをしてみませんか？