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?
Too lazy to encode/decode one symbol per cell and avoid indexes cheating, but the concept is here
tape = ['s0', '0,0,N,N,2', '1,0,E,N,1', 's1', 'N,0,W,f,1', 'f,1,W,l,1', 'l,1,W,o,1',
'o,1,W,w,1', 'w,1,W,e,1', 'e,1,W,r,1', 'r,1,N,N,HALT', 's2', '0,0,N,N,HALT', ';', '1', 'N', 'N', 'N', 'N', 'N']
def universal(tape):
awareness_index = 0
awareness_value = 'N'
current_state_value = 0
current_state_index = 'N'
separator_index = 'N'
# let's save separator index to avoid unnecessary jumps
for i, d in enumerate(tape):
if d == ';':
separator_index = i
break
counter = 0
while current_state_value != 'HALT':
counter += 1
# save state index to not parse entire tape for every instruction
if current_state_index == 'N':
for i, d in enumerate(tape):
if d == f's{current_state_value}':
current_state_index = i
for i, d in enumerate(tape[current_state_index+1:separator_index]):
awareness_value = tape[separator_index+1:][awareness_index]
# c0,mr0,aN,vN,n2'
if 's' in d:
# faced next state on the tape
break
instruction = d.split(',')
[condition, move_right, action, value, next_state] = instruction
if condition != awareness_value:
continue
if move_right == '1':
awareness_index += 1
if action == 'E':
tape[separator_index + 1 + awareness_index] = 'N'
elif action == 'W':
tape[separator_index + 1 + awareness_index] = value
current_state_value = next_state
current_state_index = 'N'
if next_state == 'HALT':
break
if counter > 50:
print('cringe happens')
break
return tape
So, to continue with machines after yesterdays offtopic, for a
Universal, the tape should look like this:
['sX', instruction, insturction, ..., ';' data]
'sX' stands for "state number X", since each state has
its own set of instructions. Then ";" acts as a separator between
instructions, and at the end is the actual data. An instuction itself
will be a string like "c0,mr0,aN,vN,n2", which..well, represents one
instruction. To make interpreter functional, we need to store two
things: current "awareness" (aka position of the head aka tape index
pointer) and current "state". That will be it?
Today is offtopic. Didn't write it today, publishing tho.. The YouTube home page is annoying; the subscriptions page is better. This little script-chrome-extension helps me fight my addiction a ton. To load this thing into Chrome locally:
chrome://extensions/background.js
chrome.webNavigation.onCommitted.addListener(
function (details) {
let url = new URL(details.url);
if (
url.href === "https://www.youtube.com/" &&
!url.href.includes("feed") &&
details.transitionType === "typed" &&
details.documentLifecycle === "active"
) {
const newUrl = `${url.origin}/feed/subscriptions`;
chrome.tabs.update(details.tabId, { url: newUrl });
}
},
{ url: [{ urlMatches: "youtube.com" }] }
);
manifest.json
{
"manifest_version": 3,
"name": "reDIRECTOR 3000",
"version": "1.0",
"permissions": ["tabs", "webNavigation"],
"background": {
"service_worker": "background.js"
}
}
Thought about an interpreter a little. Basically, to migrate a Regular
Turing machine to Universal one, I need to only move instructions from
the Machine to the tape level, and write some kind of parser for those
instructions, like: "this is the separator between different
instructions, this is how to deconstruct an instruction into its
logical parts like action, next_state, etc."
Would I like to implement it?
def interpreter(data):
[instuction, value1, value2] = data
if instuction == 'СЛОЖИ':
return value1 + value2
return 'cant interpret it'
interpreter(['СЛОЖИ', 2, 2]) # 5
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