20/08/04 18:45:38.06 lImhU2CT.net
>>165 チューリングマシン（Python3）
#チューリングマシン本体（不受理の場合例外が発生する）
def turingMachine(tape, state_function, current_state, final_state):
i=0
n = len(tape)
while i < n:
sf = state_function[current_state]
symbol = tape[i] if i >= 0 else None
(current_state, rsymbol, is_right) = sf[symbol]
if i >= 0:
tape[i] = rsymbol
if current_state == final_state:
return True
i += 1 if is_right else -1
return False
def TmMul(a, b):
#1000000の箇所はメモリ容量に合わせて適当に増やす
tape = ["0"] * a + ["1"] + ["0"] * b + ["1"] + [None] * 1000000
trans = [{"0":(6, None, True)},
{"0":(2, "X", True), "1":(4, "1", False)},
{"0":(2, "0", True), "1":(2, "1", True), None:(3, "0", False)},
{"0":(3, "0", False), "1":(3, "1", False), "X":(1, "X", True)},
{"X":(4, "0", False), "1":(5, "1", True)},
{"0":(5, "0", False), "1":(7, "1", False)},
{"0":(6, "0", True), "1":(1, "1", True)},
{"0":(8, "0", False), None:(7, None, True), "1":(9, None, True)},
{"0":(8, "0", False), None:(0, None, True)},
{"0":(9, None, True), "1":(10, None, True)}]
turingMachine(tape, trans, 0, 10)
return len(list(filter(lambda x: x != None, tape)))
print(TmMul(3, 8)) #=>24