雑感等

音楽,数学,語学,その他に関するメモを記す.

ウルフラムの2状態3シンボルチューリングマシンをpythonで実装

Wolfram's 2-state 3-symbol Turing machine - Wikipedia
Wolfram 2,3 Turing Machine Research Prize

# Wolframの2状態3シンボルユニバーサルチューリングマシン

class wolfram23tm:
    def __init__(self):
        init_len = 30  # テープの初期長
        self.tape = [0] * init_len  # テープを0で初期化
        self.head_pos = int(init_len / 2)  # ヘッド位置0で初期化
        self.head_minus = 0  # 負のヘッド位置
        self.state = "A"  # 状態"A"で初期化
        self.tape_limit = init_len + 1  # テープ長制限

    def run(self):
        while True:
            if len(self.tape) < self.tape_limit:
                head_ix = self.head_pos + self.head_minus  # ヘッド位置を配列idxとして求める
                sym, dir, sta = self.transision_function(self.state, self.tape[head_ix])
                self.tape[head_ix] = sym
                if dir == "R":
                    if head_ix < len(self.tape) - 1:
                        self.head_pos += 1
                        pass
                    else:
                        self.tape.append(0)
                        self.head_pos += 1
                    pass
                elif dir == "L":
                    if self.head_pos > 0:
                        self.head_pos -= 1
                        pass
                    else:
                        self.tape.insert(0, 0)  # テープの先頭に0を追加
                        self.head_minus += 1  # テープの先頭に要素を追加した分,ヘッド位置をずらす
                        pass
                    pass
                else:
                    exit(-1)
                pass
                self.state = sta
                print(self.tape) #毎回テープの中身を表示
            else:
                exit(-1)
                pass

    def transision_function(self, state, symbol):
        # 遷移関数
        sym, rl, sta = [], [], []
        if state == "A":
            if symbol == 0:
                sym, rl, sta = 1, "R", "B"
            elif symbol == 1:
                sym, rl, sta = 2, "L", "A"
            elif symbol == 2:
                sym, rl, sta = 1, "L", "A"
            else:
                exit(-1)
        elif state == "B":
            if symbol == 0:
                sym, rl, sta = 2, "L", "A"
            elif symbol == 1:
                sym, rl, sta = 2, "R", "B"
            elif symbol == 2:
                sym, rl, sta = 0, "R", "A"
            else:
                exit(-1)
        else:
            exit(-1)
        return sym, rl, sta


if __name__ == "__main__":
    tm = wolfram23tm()
    tm.run()
    pass