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