And if you can believe it..it's an ADVENTURE! ✶ in the domain of coding. The idea is to write some code every day during the upcoming month. Low key, just a little..
My thing will be learning about machines like Turing or Boltzmann ones (not sure that I'll be able to grasp the second one though), and prototyping my interpretations of how they work via code snippets. Probably in Python, to keep things simple?
matplotlib? Graphviz? Just print..
def visualizer(logs):
print(f"""
✶ the MACHINE state
""")
time.sleep(2.5)
for i, log in enumerate(logs):
[
state,
condition,
action,
value,
next_state,
move_to,
awareness,
tape
] = log
timer_value = 0.1 if awareness != condition else .7
timer_value2 = 0.1 if awareness != condition else .5
thing = f""" ┌────────────────────────────────────────────────────
│
│ match?: {awareness == condition}
│ condition: {condition}
│ awareness: {awareness}
│ state: {state}
│ action: {action}
│ value: {value}
│ move_to: {move_to}
│ next_state: {next_state}
│
│ tape: {tape}
│
└────────────────────────────────────────────"""
print(thing)
time.sleep(timer_value)
if i != (len(logs) - 1):
print(f""" ↓ """)
time.sleep(timer_value2)
visualizer(logs)
"Universal" is cool, but I feel an urge to read something about interpreters first before trying to write one on my own. Meanwhile I've implemented a chill version
from typing import List, Union, Literal, TypedDict, Dict
def machine(tape: List) -> List:
# "The symbol on the scanned square may be called the 'scanned symbol'
# The 'scanned symbol' is the only one of which the machine is,
# so to speak, 'directly aware'."
awareness = 0
state: Union[int, Literal["HALT"]] = 0
class Action(TypedDict):
move: List
action: Literal["WRITE", "ERASE", "NONE"]
value: Union[int, str, None]
class Instruction(TypedDict):
cond: Union[int, str, None]
do: Action
next_state: Union[int, Literal["HALT"]]
instructions: Dict[int, List[Instruction]] = {
0: [ {"cond": 0, "do": {"move": ["r", 0], "action": "NONE", "value": None}, "next_state": 2},
{"cond": 1, "do": {"move": ["r", 0], "action": "ERASE", "value": None}, "next_state": 1} ],
1: [ {"cond": None, "do": {"move": ["r", 0], "action": "WRITE", "value": "f"}, "next_state": 1},
{"cond": "f", "do": {"move": ["r", 1], "action": "WRITE", "value": "l"}, "next_state": 1},
{"cond": "l", "do": {"move": ["r", 1], "action": "WRITE", "value": "o"}, "next_state": 1},
{"cond": "o", "do": {"move": ["r", 1], "action": "WRITE", "value": "w"}, "next_state": 1},
{"cond": "w", "do": {"move": ["r", 1], "action": "WRITE", "value": "e"}, "next_state": 1},
{"cond": "e", "do": {"move": ["r", 1], "action": "WRITE", "value": "r"}, "next_state": 1},
{"cond": "r", "do": {"move": ["r", 1], "action": "NONE", "value": None}, "next_state": "HALT"} ],
2: [ {"cond": 0, "do": {"move": ["r", 0], "action": "NONE", "value": None}, "next_state": "HALT"} ]
}
while state != "HALT":
current_instructions = instructions[state]
for instruction in current_instructions:
condition = instruction["cond"]
thing_to_do = instruction["do"]
action = thing_to_do["action"]
value = thing_to_do["value"]
next_state = instruction["next_state"]
move_to = thing_to_do["move"]
if tape[awareness] != condition:
continue
[direction, step] = move_to
if direction == "r":
next_awareness = awareness + step
else:
next_awareness = awareness - step
awareness = next_awareness
if action == "WRITE":
tape[awareness] = value
elif action == "ERASE":
tape[awareness] = None
state = next_state
break # Exit the for-loop after executing the instruction
return tape
# I don't want to implement self-expanding data structure, since it's
# feels less closer to the real machine, so Noneonneoneoe
the_tape = [1, None, None, None, None, None]
machine(the_tape)
It doesn't do anything fancy, and it's not even binary-encoded. It just does stuff (erases the first symbol and writes "flower" into the tape) if tape starts with 1, and does nothing if it starts from 0. Super simple, but it encapsulates(?) the whole concept of Turing Machine. Key components:
IF, actions
ACTION and the next state STATE. In my
code snippet we have cond, do and
next_state. It's a bit odd that
ACTION/do combines both writing/erasing and moving, but
who cares
You step onto the road, keep your feet.
There are two types of Turing machines, "Regular" and "Universal". At first I thought about them as "just a function" and "high-order function which executes other functions". Well, not exactly right on an abstraction level. A closer analogy would be "hardcoded function" vs "programming language interpreter".
The main difference between these two machines is that "Regular" one contains instructions for a specific task AND those instructions are considered as part of the machine itself. "Universal" one does not contain instructions for a specific task, it reads them from the data itself.
def regular(data):
# Fixed set of instructions (part of the machine itself)
instructions = {"reverse": lambda x: x[::-1]}
result = instructions["reverse"](data)
return result
def universal(data):
for thing in data:
[instruction, variable] = thing
instruction(variable)
return
"Universal" is a chef in a restaurant (any recipe - any dish), "Regular" is a person who is trained to do french fries only (one recipe one french fry, forever, french fries universe)
Original paper by Alan Turing