Minsky Swap
Minsky Swap is an esolang based on Minsky machines and created by User:PythonshellDebugwindow.
Memory
Programs in Minsky Swap have access to two unbounded registers; however, only one of these registers can have "focus" at a time. The current register is pointed to by a register pointer.
Syntax and Semantics
Minsky Swap code is split onto two lines. The first line is the actual code to be executed and is known as the code line, and the second line contains a list of numbers and is known as the jump line. The code line is split into characters, each character being a command; the commands are listed below.
| Command | Effect |
|---|---|
+ |
Increment the register under the register pointer |
~ |
If the register under the register pointer is nonzero, decrement it; otherwise, jump to command M, where M is the Nth number in the jump line and this ~ is the Nth tilde in the code line
|
* |
Swap the register pointer between the first and second register |
Readable Minsky Swap Notation
Readable Minsky Swap Notation (RMSN) is a more readable notation for Minsky Swap. It is reminiscent of Portable Minsky Machine Notation. In RMSN, each command is on one line. inc(); increments the current register; decnz(N); decrements the current register if it's nonzero, and jumps to line N (1-based) otherwise; and swap(); swaps the register pointer.
Computational class
The halting problem for Minsky Swap is equivalent to the halting problem for a standard 1-counter Minsky machine, which is just a push-down automaton with 1 symbol.
Conversion from MS to 1-c MM:
An increment or a successful decrement must continue to the next command. So, letting L denote the number of commands, if both registers are L or greater, the program must halt. The remaining possible states of the program can be translated like so:
- If both registers are less than L, there are only a finite number of states, so this can be encoded with a finite-state machine.
- If one register (call it X) is L or greater, use the counter to represent X-L. When it returns to 0, switch back to the finite behavior.
Conversion from 1-c MM to MS:
To increment the counter: +
The other register will be kept at 0 and only used for control flow.
Suppose D is a command to decrement the counter, which jumps to X if successful, and Y if not. In Minsky Swap, this can be encoded by:
D -> ~Y * ~X X -> * X * Y -> Y
where the letter after a ~ indicates the point to jump to. If J is a command to jump to X unconditionally:
J -> * ~X X -> * X *
From there, it's possible to build arbitrary control structures.