Structured Minsky
| Paradigm(s) | imperative |
|---|---|
| Designed by | stkptr |
| Appeared in | 2023 |
| Memory system | counters |
| Dimensions | one-dimensional |
| Computational class | Turing complete |
| Reference implementation | Unimplemented |
| Influenced by | PMMN |
| File extension(s) | .sm, .smmn |
Structured Minsky is a restricted variant of Portable Minsky Machine Notation.
Structure
A Structured Minsky machine SM(n) has n many counters, as well as a conditional bit and a temp bit.
The following commands are available in Structured Minsky:
| Command | Effect |
|---|---|
+n |
increment counter n, where n is any nonnegative integer |
-n |
decrement counter n, set conditional if n changed value, else clear |
[ |
if conditional bit is cleared, skip forwards to matching ], else continue |
] |
skip backwards to matching [ |
! |
unconditionally flip conditional bit |
x |
swap conditional bit and temp bit |
c |
copy conditional bit to temp bit |
The construction -n [{code} -n] is therefore identical to the while construct in PMMN.
Using these the if structure can be created:
-n
[ +n -n ! c
{code}
+n -n ! c
]
Such that n is the counter to test. Oneshot execution is accomplished by setting the conditional bit to 0. To do this the construct +n -n, which always results in a change of value on decrement without an ultimate change to n, is used to set the bit. ! inverts the always set to be an always clear. c copies it to ensure that the temp bit is also 0. The copy operation, as well as the duplication of the construct at the beginning of the loop, are not strictly necessary.
If-else can be constructed in this manner (for counter n):
-n
c
!
[
+n -n ! c
{else}
+n -n ! c
]
x
[ +n -n ! c
{if}
+n -n ! c
]
Turing completeness
Since any PMMN program can be converted into Structured Minsky, it is therefore Turing complete. Further, since a Minsky machine with two counters is Turing complete, SM(n) for n ≥ 2 is also Turing complete.
Variants
The temp bit can be swapped for a counter. The ! should be possible to remove in a similar way.