Mutt Machine
Mutt machine is a computational model invented by User:RainbowDash in 2025.
Overview
Mutt machine works on a tape of symbols. Symbols are viewed on the right of tape and appended to the left. Any amount of symbols can be read from the right but only one is removed at a time from the right. The viewed symbols, decide the symbols appended on the left of the tape. Alternatively the read head can choose to print the right-most symbol to a console and append more symbols, halt the machine, or read an input symbol from the user.
Another halting state is when you read something, and there is no rule to write something. As in there is no mapping from the read symbols into an appending.
Rules are executed in a cyclic manner forever and ever until the program halts there is no branching.
Example
|
|
Execution History
Initial tape [A,B,B,A] 1. [A, B] :: [B, A] ## Rule 1, Read B,A 2. [A, A] :: [B, B] ## Rule 2, Read B,A 3. [A] :: [A, B] ## Rule 1, Read A,B 4. [A] :: [A, A] ## Rule 2, Read A,A 5. [A, A] ## Rule 1, Read A,A 6. [B, A] ## Rule 2, Read B,A 7. [A, B] ## Rule 1, Read A,B 8. [A, A] ## Rule 2, Read A,A 9. [A] ## Rule 1, Can't read 2 symbols now halting. ** Machine halted **
An absurd rule that can still can work under this machine's rules.
| Read | Write |
|---|---|
| A,A,C,A,B | HALT |
| A,B | A,A,C,A,B |
| 53 | |
| 53 | PRINT, APPEND 53 |
Branchless Programming
A ruleset with integers can emulate a RAM machine.
Rules such as
| Read | Write |
|---|---|
| 0,1 | 1 |
| 0,2 | 2 |
| ... | ... |
| 255,254 | 509 |
| 255,255 | 510 |
which reads two numbers and adds the sum on the left.
We can continue this to NOP ADD SUBTRACT EQUALS FLOORDIV MULT HALT IF EQUAL TO ZERO HALT PRINT INC DEC
then we can compile a simple ASM program to this. Windmill style programs can also work with this allowing for Turing complete programs with integers allowing for loops instead of a Total program.
For example an ASM program that checks if two numbers are equal
SET 0 A # This is input A SET 1 B # This is input B SET 6 1 SET 7 2 SET 5 1 COPY 0 2 SUB 1 2 COPY 2 3 MULT 2 3 COPY 3 4 ADD 6 4 MULT 7 3 DIV 4 3 SUB 3 5 PRINT 5
Compiles roughly to
init_tape = [5, 9, 0, 0, 0, 1, 1, 2, 0, 0, 0, 0] [NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, COPY, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SUB, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, COPY, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, COPY, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, MULT, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, COPY, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, ADD, NOP, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, MULT, NOP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, SWAP, DIV, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, COPY, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, SWAP, SWAP, SUB, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, COPY, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, NOP, PRINT, HALT]
which roughly would be around 13330125 different rewriting transitions if all written out in cyclic order. However the swap instruction would take more than 1 instruction so it would be a bit more.