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.
||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 |
||Swap the register pointer|
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.
The halting problem for Minsky Swap can be reduced to the halting problem for a standard 1-counter Minsky machine, which is solvable. Therefore, Minsky Swap is sub-Turing.
Proof: 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.