Automata Based Paradigm#
Initial Set-Up#
from automata.tm.dtm import DTM
def int_to_unary(number: int) -> str:
return "0" * number
def unary_to_int(number: str) -> int:
return len(number)
Predecessor and Successor#
def predecessor(a: int) -> int:
dtm = DTM(
states={"q0", "q1", "q2"},
input_symbols={"0"},
tape_symbols={"0", "."},
transitions={
"q0": {"0": ("q0", "0", "R"), ".": ("q1", ".", "L")},
"q1": {".": ("q1", ".", "L"), "0": ("q2", ".", "L")},
},
initial_state="q0",
blank_symbol=".",
final_states={"q2"},
)
input_string = int_to_unary(a)
result, *_ = "".join(dtm.read_input(input_string).tape.tape).split(".")
return unary_to_int(result)
assert predecessor(1) == 0
assert predecessor(10) == 9
def successor(a: int) -> int:
dtm = DTM(
states={"q0", "q1"},
input_symbols={"0"},
tape_symbols={"0", "."},
transitions={
"q0": {"0": ("q0", "0", "R"), ".": ("q1", "0", "R")},
},
initial_state="q0",
blank_symbol=".",
final_states={"q1"},
)
input_string = int_to_unary(a)
result, *_ = "".join(dtm.read_input(input_string).tape.tape).split(".")
return unary_to_int(result)
assert successor(0) == 1
assert successor(10) == 11
Addition#
def addition(addend_1: int, addend_2: int) -> int:
# Implementation from https://www.geeksforgeeks.org/turing-machine-addition/
dtm = DTM(
states={"q0", "q1", "q2", "q3", "q4", "q5"},
input_symbols={"0", "c"},
tape_symbols={"0", "x", "c", "."},
transitions={
"q0": {"0": ("q1", "x", "R"), "c": ("q5", ".", "R")},
"q1": {"0": ("q1", "0", "R"), "c": ("q2", "c", "R")},
"q2": {"0": ("q2", "0", "R"), ".": ("q3", "0", "L")},
"q3": {"0": ("q3", "0", "L"), "c": ("q4", "c", "L")},
"q4": {"0": ("q4", "0", "L"), "x": ("q0", "x", "R")},
},
initial_state="q0",
blank_symbol=".",
final_states={"q5"},
)
input_string = f"{int_to_unary(addend_1)}c{int_to_unary(addend_2)}"
*_, result = "".join(dtm.read_input(input_string).tape.tape).split(".")
return unary_to_int(result)
assert addition(0, 0) == 0
assert addition(1, 0) == 1
assert addition(0, 1) == 1
assert addition(10, 10) == 20
Step by Step Breakdown#
dtm = DTM(
states={"q0", "q1", "q2", "q3", "q4", "q5"},
input_symbols={"0", "c"},
tape_symbols={"0", "x", "c", "."},
transitions={
"q0": {"0": ("q1", "x", "R"), "c": ("q5", ".", "R")},
"q1": {"0": ("q1", "0", "R"), "c": ("q2", "c", "R")},
"q2": {"0": ("q2", "0", "R"), ".": ("q3", "0", "L")},
"q3": {"0": ("q3", "0", "L"), "c": ("q4", "c", "L")},
"q4": {"0": ("q4", "0", "L"), "x": ("q0", "x", "R")},
},
initial_state="q0",
blank_symbol=".",
final_states={"q5"},
)
for step in list(dtm.read_input_stepwise("00c00")):
print(step)
TMConfiguration('q0', TMTape('00c00', 0))
TMConfiguration('q1', TMTape('x0c00', 1))
TMConfiguration('q1', TMTape('x0c00', 2))
TMConfiguration('q2', TMTape('x0c00', 3))
TMConfiguration('q2', TMTape('x0c00', 4))
TMConfiguration('q2', TMTape('x0c00.', 5))
TMConfiguration('q3', TMTape('x0c000', 4))
TMConfiguration('q3', TMTape('x0c000', 3))
TMConfiguration('q3', TMTape('x0c000', 2))
TMConfiguration('q4', TMTape('x0c000', 1))
TMConfiguration('q4', TMTape('x0c000', 0))
TMConfiguration('q0', TMTape('x0c000', 1))
TMConfiguration('q1', TMTape('xxc000', 2))
TMConfiguration('q2', TMTape('xxc000', 3))
TMConfiguration('q2', TMTape('xxc000', 4))
TMConfiguration('q2', TMTape('xxc000', 5))
TMConfiguration('q2', TMTape('xxc000.', 6))
TMConfiguration('q3', TMTape('xxc0000', 5))
TMConfiguration('q3', TMTape('xxc0000', 4))
TMConfiguration('q3', TMTape('xxc0000', 3))
TMConfiguration('q3', TMTape('xxc0000', 2))
TMConfiguration('q4', TMTape('xxc0000', 1))
TMConfiguration('q0', TMTape('xxc0000', 2))
TMConfiguration('q5', TMTape('xx.0000', 3))
# Addition of 2+2
# 2 + 2 => 00c00
# '0'c00 # Q0 -> Q1
# x'0'c00 # Q1 -> Q1
# x0'c'00 # Q1 -> Q2
# x0c'0'0 # Q2 -> Q2
# x0c0'0' # Q2 -> Q2
# x0c00' ' # Q2 -> Q3
# x0c0'0'0 # Q3 -> Q3
# x0c'0'00 # Q3 -> Q3
# x0'c'000 # Q3 -> Q4
# x'0'c000 # Q4 -> Q4
# 'x'0c000 # Q4 -> Q0
# x'0'c000 # Q0 -> Q1
# xx'c'000 # Q1 -> Q2
# xxc'0'00 # Q2 -> Q2
# xxc0'0'0 # Q2 -> Q2
# xxc00'0' # Q2 -> Q2
# xxc000' ' # Q2 -> Q3
# xxc00'0'0 # Q3 -> Q3
# xxc0'0'00 # Q3 -> Q3
# xxc'0'000 # Q3 -> Q3
# xx'c'0000 # Q3 -> Q4
# x'x'c0000 # Q4 -> Q0
# xx'c'0000 # Q0 -> Q5
# xx.'0'000 # Q5
Multiplication#
def multiplication(multiplicand: int, multiplier: int) -> int:
dtm = DTM(
states={
"q0",
"q1",
"q2",
"q3",
"q4",
"q5",
"q6",
"q7",
"q8",
"q9",
"q10",
"q11",
"q12",
},
input_symbols={"0", "x", "="},
tape_symbols={"0", "x", "y", ".", "="},
transitions={
"q0": {"0": ("q1", "x", "R"), "x": ("q11", "x", "L")},
"q1": {"0": ("q1", "0", "R"), "x": ("q2", "x", "R")},
"q2": {"=": ("q3", "=", "L"), "0": ("q4", "y", "R")},
"q3": {"y": ("q3", "0", "L"), "x": ("q9", "x", "L")},
"q4": {"0": ("q4", "0", "R"), "=": ("q5", "=", "R")},
"q5": {"0": ("q5", "0", "R"), ".": ("q6", "0", "L")},
"q6": {"0": ("q6", "0", "L"), "=": ("q7", "=", "L")},
"q7": {"0": ("q7", "0", "L"), "y": ("q8", "y", "R")},
"q8": {"0": ("q4", "y", "R"), "=": ("q3", "=", "L")},
"q9": {"0": ("q9", "0", "L"), "x": ("q0", "x", "R")},
"q11": {"x": ("q11", "0", "L"), ".": ("q12", ".", "R")},
},
initial_state="q0",
blank_symbol=".",
final_states={"q12"},
)
input_string = f"{int_to_unary(multiplicand)}x{int_to_unary(multiplier)}="
*_, result = "".join(dtm.read_input(input_string).tape.tape).split("=")
return unary_to_int(result)
assert multiplication(0, 0) == 0
assert multiplication(2, 0) == 0
assert multiplication(0, 2) == 0
assert multiplication(10, 10) == 100
dtm = DTM(
states={
"q0",
"q1",
"q2",
"q3",
"q4",
"q5",
"q6",
"q7",
"q8",
"q9",
"q10",
"q11",
"q12",
},
input_symbols={"0", "x", "="},
tape_symbols={"0", "x", "y", ".", "="},
transitions={
"q0": {"0": ("q1", "x", "R"), "x": ("q11", "x", "L")},
"q1": {"0": ("q1", "0", "R"), "x": ("q2", "x", "R")},
"q2": {"=": ("q3", "=", "L"), "0": ("q4", "y", "R")},
"q3": {"y": ("q3", "0", "L"), "x": ("q9", "x", "L")},
"q4": {"0": ("q4", "0", "R"), "=": ("q5", "=", "R")},
"q5": {"0": ("q5", "0", "R"), ".": ("q6", "0", "L")},
"q6": {"0": ("q6", "0", "L"), "=": ("q7", "=", "L")},
"q7": {"0": ("q7", "0", "L"), "y": ("q8", "y", "R")},
"q8": {"0": ("q4", "y", "R"), "=": ("q3", "=", "L")},
"q9": {"0": ("q9", "0", "L"), "x": ("q0", "x", "R")},
"q11": {"x": ("q11", "0", "L"), ".": ("q12", ".", "R")},
},
initial_state="q0",
blank_symbol=".",
final_states={"q12"},
)
for step in list(dtm.read_input_stepwise("00x000=")):
print(step)
TMConfiguration('q0', TMTape('00x000=', 0))
TMConfiguration('q1', TMTape('x0x000=', 1))
TMConfiguration('q1', TMTape('x0x000=', 2))
TMConfiguration('q2', TMTape('x0x000=', 3))
TMConfiguration('q4', TMTape('x0xy00=', 4))
TMConfiguration('q4', TMTape('x0xy00=', 5))
TMConfiguration('q4', TMTape('x0xy00=', 6))
TMConfiguration('q5', TMTape('x0xy00=.', 7))
TMConfiguration('q6', TMTape('x0xy00=0', 6))
TMConfiguration('q7', TMTape('x0xy00=0', 5))
TMConfiguration('q7', TMTape('x0xy00=0', 4))
TMConfiguration('q7', TMTape('x0xy00=0', 3))
TMConfiguration('q8', TMTape('x0xy00=0', 4))
TMConfiguration('q4', TMTape('x0xyy0=0', 5))
TMConfiguration('q4', TMTape('x0xyy0=0', 6))
TMConfiguration('q5', TMTape('x0xyy0=0', 7))
TMConfiguration('q5', TMTape('x0xyy0=0.', 8))
TMConfiguration('q6', TMTape('x0xyy0=00', 7))
TMConfiguration('q6', TMTape('x0xyy0=00', 6))
TMConfiguration('q7', TMTape('x0xyy0=00', 5))
TMConfiguration('q7', TMTape('x0xyy0=00', 4))
TMConfiguration('q8', TMTape('x0xyy0=00', 5))
TMConfiguration('q4', TMTape('x0xyyy=00', 6))
TMConfiguration('q5', TMTape('x0xyyy=00', 7))
TMConfiguration('q5', TMTape('x0xyyy=00', 8))
TMConfiguration('q5', TMTape('x0xyyy=00.', 9))
TMConfiguration('q6', TMTape('x0xyyy=000', 8))
TMConfiguration('q6', TMTape('x0xyyy=000', 7))
TMConfiguration('q6', TMTape('x0xyyy=000', 6))
TMConfiguration('q7', TMTape('x0xyyy=000', 5))
TMConfiguration('q8', TMTape('x0xyyy=000', 6))
TMConfiguration('q3', TMTape('x0xyyy=000', 5))
TMConfiguration('q3', TMTape('x0xyy0=000', 4))
TMConfiguration('q3', TMTape('x0xy00=000', 3))
TMConfiguration('q3', TMTape('x0x000=000', 2))
TMConfiguration('q9', TMTape('x0x000=000', 1))
TMConfiguration('q9', TMTape('x0x000=000', 0))
TMConfiguration('q0', TMTape('x0x000=000', 1))
TMConfiguration('q1', TMTape('xxx000=000', 2))
TMConfiguration('q2', TMTape('xxx000=000', 3))
TMConfiguration('q4', TMTape('xxxy00=000', 4))
TMConfiguration('q4', TMTape('xxxy00=000', 5))
TMConfiguration('q4', TMTape('xxxy00=000', 6))
TMConfiguration('q5', TMTape('xxxy00=000', 7))
TMConfiguration('q5', TMTape('xxxy00=000', 8))
TMConfiguration('q5', TMTape('xxxy00=000', 9))
TMConfiguration('q5', TMTape('xxxy00=000.', 10))
TMConfiguration('q6', TMTape('xxxy00=0000', 9))
TMConfiguration('q6', TMTape('xxxy00=0000', 8))
TMConfiguration('q6', TMTape('xxxy00=0000', 7))
TMConfiguration('q6', TMTape('xxxy00=0000', 6))
TMConfiguration('q7', TMTape('xxxy00=0000', 5))
TMConfiguration('q7', TMTape('xxxy00=0000', 4))
TMConfiguration('q7', TMTape('xxxy00=0000', 3))
TMConfiguration('q8', TMTape('xxxy00=0000', 4))
TMConfiguration('q4', TMTape('xxxyy0=0000', 5))
TMConfiguration('q4', TMTape('xxxyy0=0000', 6))
TMConfiguration('q5', TMTape('xxxyy0=0000', 7))
TMConfiguration('q5', TMTape('xxxyy0=0000', 8))
TMConfiguration('q5', TMTape('xxxyy0=0000', 9))
TMConfiguration('q5', TMTape('xxxyy0=0000', 10))
TMConfiguration('q5', TMTape('xxxyy0=0000.', 11))
TMConfiguration('q6', TMTape('xxxyy0=00000', 10))
TMConfiguration('q6', TMTape('xxxyy0=00000', 9))
TMConfiguration('q6', TMTape('xxxyy0=00000', 8))
TMConfiguration('q6', TMTape('xxxyy0=00000', 7))
TMConfiguration('q6', TMTape('xxxyy0=00000', 6))
TMConfiguration('q7', TMTape('xxxyy0=00000', 5))
TMConfiguration('q7', TMTape('xxxyy0=00000', 4))
TMConfiguration('q8', TMTape('xxxyy0=00000', 5))
TMConfiguration('q4', TMTape('xxxyyy=00000', 6))
TMConfiguration('q5', TMTape('xxxyyy=00000', 7))
TMConfiguration('q5', TMTape('xxxyyy=00000', 8))
TMConfiguration('q5', TMTape('xxxyyy=00000', 9))
TMConfiguration('q5', TMTape('xxxyyy=00000', 10))
TMConfiguration('q5', TMTape('xxxyyy=00000', 11))
TMConfiguration('q5', TMTape('xxxyyy=00000.', 12))
TMConfiguration('q6', TMTape('xxxyyy=000000', 11))
TMConfiguration('q6', TMTape('xxxyyy=000000', 10))
TMConfiguration('q6', TMTape('xxxyyy=000000', 9))
TMConfiguration('q6', TMTape('xxxyyy=000000', 8))
TMConfiguration('q6', TMTape('xxxyyy=000000', 7))
TMConfiguration('q6', TMTape('xxxyyy=000000', 6))
TMConfiguration('q7', TMTape('xxxyyy=000000', 5))
TMConfiguration('q8', TMTape('xxxyyy=000000', 6))
TMConfiguration('q3', TMTape('xxxyyy=000000', 5))
TMConfiguration('q3', TMTape('xxxyy0=000000', 4))
TMConfiguration('q3', TMTape('xxxy00=000000', 3))
TMConfiguration('q3', TMTape('xxx000=000000', 2))
TMConfiguration('q9', TMTape('xxx000=000000', 1))
TMConfiguration('q0', TMTape('xxx000=000000', 2))
TMConfiguration('q11', TMTape('xxx000=000000', 1))
TMConfiguration('q11', TMTape('x0x000=000000', 0))
TMConfiguration('q11', TMTape('.00x000=000000', 0))
TMConfiguration('q12', TMTape('.00x000=000000', 1))
Exponentiation#
def exponentiation(base: int, exponent: int) -> float:
# Potential implementation in https://philarchive.org/archive/LEMATM
raise NotImplementedError
assert exponentiation(1, 0) == 1
assert exponentiation(0, 1) == 0
assert exponentiation(3, 3) == 27
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call last)
Cell In[10], line 6
1 def exponentiation(base: int, exponent: int) -> float:
2 # Potential implementation in https://philarchive.org/archive/LEMATM
3 raise NotImplementedError
----> 6 assert exponentiation(1, 0) == 1
7 assert exponentiation(0, 1) == 0
8 assert exponentiation(3, 3) == 27
Cell In[10], line 3, in exponentiation(base, exponent)
1 def exponentiation(base: int, exponent: int) -> float:
2 # Potential implementation in https://philarchive.org/archive/LEMATM
----> 3 raise NotImplementedError
NotImplementedError: