Minsky Swap

From Esolang
Jump to navigation Jump to search

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

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 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.

Implementations

A Python interpreter by User:Bangyen.