We are currently working on new rules for what content should and shouldn't be allowed on this website, and are looking for feedback! See Esolang:2026 topicality proposal to view and give feedback on the current draft.
S^A machine
Jump to navigation
Jump to search
S^A machine is designed by PSTF, which is a subset of a Minsky machine with 2 registers.
Why S^A?
The English name of PSTF is Stephen Abel.
Definition
A S^A machine consists of 2 registers called A and B and the following 9 operations.
- Increase the value of A by 1
- Decrease the value of A by 1 if A>0 else do nothing
- Swap the values of A and B
- Apply all operations on A to B instead
- Apply all operations on B back to A
- If A is 0, jump to line x, where x is a constant
- Transfer the value of A to the screen
- Transfer the input value to A
- Jump to line x, where x is a constant
As the definition shown, any S^A machine can be represented by these operations:
1 + 2 - 3 % 4 > 5 < 6 ?x 7 . 8 , 9 !x
Computational Class
This model is Turing complete (specifically, it is equivalent to a 2‑counter Minsky machine, which has the same expressive power as a Turing machine).
Proof
- There are two main registers, A and B.
- Initially, all operations are done on A, and the two main operations are 'add' and 'subtract', both of which are basic operations supported by a Minsky machine.
- Operations on B can be done using the 'Convert' command. After running this command, all operations that were originally on A (add, subtract, in, and out) will switch to affect B.
- You might have noticed that there’s no mention of a 'zero check' in what was mentioned above, but that can also be done — just swap the values of A and B, and then A's value will be B's original value, so you can check through A whether B was originally 0.
- The input and output can be neglected.
- Q.E.D. The S^A machine is basically a two-register Minsky machine.
- Since a 2‑counter Minsky machine is known to be Turing complete (it can simulate a Turing machine, given unbounded counters), and all its instructions are directly implementable in this model, the model is Turing complete.
Note: This assumes the registers hold unbounded non‑negative integers, which is the standard assumption for counter machines.
Equivalent of Minsky Machine
Minsky S^A INC A + DEC A - JZ A,x ?x INC B >+< DEC B >-< JZ B,x >?x< JMP x !x
Implementation in Python
Note: Used another command set.
class Machine:
def __init__(self):
self.reset()
def reset(self):
# The 4 registers
self.A = 0
self.B = 0
self.I = 0 # input
self.O = 0 # output
# Active register for INC/DEC ('A' or 'B')
self.mode = 'A'
# Program counter
self.pc = 0
# Internal storage
self.code = []
self.labels = {}
def load(self, source):
"""
Load assembly source code (list of strings).
Supports labels (e.g., 'LOOP:') and comments (starting with #).
"""
self.labels = {}
cleaned = []
# First pass: remove comments, empty lines, collect labels
for idx, line in enumerate(source):
line = line.split('#')[0].strip()
if not line:
continue
# Check for label
if ':' in line:
label, instr = line.split(':', 1)
self.labels[label.strip()] = len(cleaned)
line = instr.strip()
if not line:
continue
parts = line.split()
op = parts[0].upper()
arg = None
if len(parts) > 1:
arg = parts[1]
# Try to convert to int; if fails, it's a label (resolved later)
try:
arg = int(arg)
except ValueError:
pass
cleaned.append((op, arg))
# Second pass: resolve label references to line numbers
self.code = []
for op, arg in cleaned:
if isinstance(arg, str) and arg in self.labels:
arg = self.labels[arg]
self.code.append((op, arg))
def run(self, input_val=None):
"""Execute the loaded program. Optionally set input register I."""
if input_val is not None:
self.I = input_val
self.pc = 0
while 0 <= self.pc < len(self.code):
op, arg = self.code[self.pc]
self.pc += 1 # default: next instruction
# ---- Core instructions ----
if op == 'INC':
if self.mode == 'A':
self.A += 1
else:
self.B += 1
elif op == 'DEC':
if self.mode == 'A':
if self.A > 0:
self.A -= 1
else:
if self.B > 0:
self.B -= 1
elif op == 'SWAP':
self.A, self.B = self.B, self.A
elif op == 'MODE_B': # "Apply all operations on A to B instead"
self.mode = 'B'
elif op == 'MODE_A': # "Apply all operations on B back to A"
self.mode = 'A'
elif op == 'JZ': # "If A is 0, jump to line x"
if self.A == 0:
self.pc = arg
elif op == 'JMP': # unconditional jump
self.pc = arg
elif op == 'IN': # "Transfer I to A"
self.A = self.I
elif op == 'OUT': # "Transfer A to O"
self.O = self.A
else:
raise RuntimeError(f"Unknown instruction: {op}")
return self.O
# ======================================================
# Example program: read I, multiply it by 2, output result
# ======================================================
demo_source = [
"IN", # A = I (e.g., 5)
"SWAP", # A=0, B=5 (clears A, moves input to B)
"LOOP:", # label
"JZ END", # if A (counter) == 0, jump to END
"DEC", # A -= 1
"MODE_B", # now INC/DEC affect B
"INC", # B += 1
"INC", # B += 1 → total +2 per loop iteration
"MODE_A", # switch back to A
"JMP LOOP",
"END:",
"SWAP", # A = result (2*I), B = 0
"OUT" # O = A
]
if __name__ == "__main__":
m = Machine()
m.load(demo_source)
result = m.run(input_val=5)
print(f"Output: {result}") # prints 10