Minsky Machine to DownRight translation

Here are User:Keymaker's two Minsky machine into DownRight translations, from 2018 and 2019, although they were not published until 2025. Although DownRight has long since been shown Turing-complete, these translations provide an alternative proof of it. The translations were made, however, just for the sake of making them and being able to see programs running in a visual interpreter.

This page uses characters v and > for down and right arrows because all of the author's notes and programs use that, for technical reasons. If the target software requires it, they can be substituted with the arrows DownRight uses.

First version (2018)

The first version is a more inefficient one, based on storing two registers in a single integer, encoded with primes 2 and 3. It is more difficult to understand and decipher, and the author cannot be bothered to go into details after all this time. The translation does not feature halting, either. It creates a matrix with width 18 and its height depending on the size of the input program.

The translator can be found here: http://yiap.nfshost.com/esoteric/downright/oldmmtodr.py

This MM program

1 inc A 2
2 dec A 2 1

translated into DownRight and then into a web-runnable interpreter (using drintgen) can be examined here: http://yiap.nfshost.com/esoteric/downright/mm1.html

Second version (2019)

The second construction is better. It can use all of the registers as they are in the original Minsky Machine program (so it does not require transforming the program to use only two registers, unlike the first version). There are advantages of speed and storage as well. The height of the matrix is 4 and the width depends on the size of the input program.

A counter is encoded as 2^n units (which are four down arrows, "vvvv") in a row, where n is the counter's value. Value 0 is "vvvv", 1 is "vvvvvvvv", 2 is 4*"vvvv", 3 is 8*"vvvv", and so forth.

Essentially the program goes through the counters and enqueues them in identical form if the simulated instruction is not in the process of changing them. To increase a counter, for every unit of the counter two units are appended to the memory. To decrease a counter, it is halved. This means, in this context, appending only "vv" for every full unit. Once value 0 ("vvvv") is processed this way, it stores only "vv" in the memory, opposed to a value consisting of whole "vvvv" units created by all other values. After halving the counter, it is inspected. A counter containing a value not dividable by four (that is "vv", zero's value after halving), will shift the program pointer to a location it never travels with ordinary values. The half-unit is restored into a full unit ("vvvv") and the program execution branches (the different target of the next instruction is already placed at the end of the memory before the memory-restoration cycle begins).

Halting removes all the data in the memory, to effect a halt in DownRight (the empty queue). The values of the counters, thus, need to be inspected right before the halting procedure begins erasing data.

The translator can be found here: http://yiap.nfshost.com/esoteric/downright/ammdr.py

This MM program

1 inc A 2
2 inc A 3
3 dec A 4 5
4 inc B 3
5 halt

translated into DownRight and then put through drintgen can be seen here: http://yiap.nfshost.com/esoteric/downright/mm2.html

Open question

Open question: Can Minsky Machine be translated into DownRight with some construction that uses less memory than 2^n units per counter?

Note on tools

Both of these translators create output in a format readable by User:Keymaker's other DownRight tools, such as the visual interpreter generator (drintgen). These tools can be found on the DownRight page.