The Amnesiac From Minsk
The Amnesiac From Minsk is a series of esoteric programming languages designed by User:ais523 towards the end of 2015. They are arranged as a sequence of "difficulty levels"; higher-level languages are intended to be harder to program in (and lower-level languages can be seen as wimpmodes for the higher-level languages). Minsky machines can be seen as a "level 0", or a wimpmode for the language as a whole, as they have a strict superset of its functionality.
In addition to the obvious Minsky machines, inspirations for the language include StackFlow and :≠. It's also less directly inspired by Three Star Programmer and MiniMAX, via Last ReSort.
The Amnesiac From Minsk, level 1
Semantics
At level 1, a The Amnesiac From Minsk program consists of a set of counters, each of which is initialized to a value specified in the program. Each counter can hold an unbounded positive integer (i.e. 0 is not a valid value, so a counter will fail to decrement from 1). The other thing that the program specifies is a list of triggers for each counter: one that runs when the counter is incremented, one which runs when the counter is decremented, and one which runs when an attempt is made to decrement the counter, but which fails because the counter's value is 1.
The triggers work in a very similar way to in :≠; when the counter is changed, the corresponding trigger will run immediately afterwards. Unlike in :≠, recursion is allowed, i.e. it's legal for a trigger on a counter to start a cascading chain of triggers that results in another change to that same counter. However, again unlike in :≠, the triggers are tail calls (and thus none of the usual state for tracking recursion is required to implement The Amnesiac From Minsk); the trigger does not return after it runs (or at any other time). Given that every possible change to a counter (and thus everything that you can do in the language) will trigger some trigger or other, this means that there's no point in the code for a trigger containing more than one command, as the first command will never return. (These rules are the same as those used for pop commands in StackFlow.)
The program halts if a counter is incremented, and the trigger for that increment causes the same counter to be incremented again. (At this point, it is clear that the program is incapable of making further progress.) Likewise, it halts if a counter fails to decrement from 1, and the trigger for that decrement causes an attempt to be made to decrement that same counter again. The implementation starts by incrementing the first counter, and allowing the program to run its course via triggers from there.
As an extension, if a program contains precisely two counters that are not decremented by any trigger, incrementing the one that appears earlier in the program will write a 0 bit to standard output, and incrementing the one that appears later in the program will write a 1 bit to standard output. In the common case where implementations write bits an octet at a time, they should write bits that appear earlier at the more significant end of the byte.
Syntax
Syntactically, the language looks like this:
L1 + = - 0: +1; +2; -1; @5 1: -0; -2; -1; @9 This is a comment. 2: +0; +1; -0; @12
Horizontal whitespace is insignificant anywhere, except that it's disallowed in the middle of a literal integer (although programmers are encouraged to make the columns line up); vertical whitespace is significant. The first line must consist of L1+=-, typically with whitespace added. Each subsequent line starts with a nonnegative integer (the counter number), in sequence starting at 0 and ascending from there. This is followed by the triggers for increment, failed decrement, successful decrement, separated by semicolons; then a semicolon, @, and the initial value for the counter. Anything beyond that is a comment, and should be ignored by implementations. The triggers themselves are expressed as + or - (for increment and for decrement attempt, respectively), followed by the number of the counter to affect.
Implementation in and of other languages
A level 1 The Amnesiac From Minsk program is clearly a special case of a Minsky machine (specifically, one in which the program does not have to remember why it tried to increment or decrement a given counter, because all the information is provided with knowledge of what it's currently doing, thus "amnesiac").
Slightly less obviously, but nonetheless with a pretty direct construction, you can compile any level 1 The Amnesiac From Minsk program into StackFlow via representing a counter as a stack with one distinguished symbol at the bottom (that re-pushes itself upon an attempt to pop it) and a different symbol for the other elements of the stack. The "successful decrement" and "failed decrement" triggers have exact analogues in StackFlow (the rules for the "not bottom of stack" and "bottom of stack" symbols for the stack that corresponds to the counter). The "increment" trigger does not directly have an analogue, but because a StackFlow rule can contain multiple push commands, it is possible to simply inline the trigger into every rule that increments the counter corresponding to the stack.
Going the other way, The Amnesiac From Minsk can be proved Turing complete at level 1 via implementing Minsky machines in it. The construction works like this: we treat the Minsky machine as a set of counters, plus a state machine that remembers what the system is currently doing. For each state of the state machine, we have a counter that is normally 1, but is 2 while that state is executing. These are connected in chains via failed-decrement triggers; thus attempting to decrement the first counter in a chain will set every counter in the chain to 1 and run the successful-decrement trigger for the current state (if that state is in the chain).
This gives a way to increment counters without losing state, using an "increment chain" for all states that do an increment: you increment the counter for the state, have its increment trigger increment the data counter you wanted to increment, have its increment trigger attempt to decrement the first counter in the increment chain, and have the successful-decrement trigger increment the counter for the next state, and so on. It can be seen by inspection that each trigger in the chain is only used for one purpose, meaning that we have no clashes and thus arbitrary increment behaviour will work.
For decrements, things are rather more complex; we can't use the same construction directly because a decrement has two possible results. Instead, we have two chains: "successful decrement" (which contains one element per decrementing state), and "failed decrement" (which also contains one element per decrementing state). Additionally, we have two separate counters, "success control" and "failure control", for each decrementing state. As with the implementation of increments, these are all 1 except when a decrement is in progress. You start a decrement via incrementing the "succesful decrement" element for the current state, which (via its increment trigger) increments the "failed decrement" element for the current state, which decrements the data counter in question. Its triggers then attempt to decrement the first element of either the "successful decrement" or "failed decrement" chain, depending on the success or failure of the decrement.
The failed-decrement triggers for these two chains are used to maintain the chain behaviour. The successful-decrement triggers for the "successful decrement" and "failed decrement" chains attempt to decrement the "failure control" or "success control" counter respectively for the state in question. Each of these counters will increment the other on a failed decrement, attempt to decrement the first element of the "succesful decrement" or "failed decrement" chain respectively on an increment, and move onto the next state (via incrementing an appropriate chain element to start its increment or decrement) on successful decrement.
Here's an example to show how this works, using a successful decrement in the third state in the chain:
s.dec chain f.dec chain s.control f.control 11111...111 11111...111 1 1 Before starting the decrement 11211...111 11111...111 1 1 Decrement starts from outside 11211...111 11211...111 1 1 After the first trigger --- Data counter decremented here, and decrements the s.dec chain --- 11111...111 11211...111 1 1 f.control fails to decrement 11111...111 11211...111 2 1 so it increments s.control 11111...111 11111...111 2 1 which decrements f.dec chain 11111...111 11111...111 1 1 s.control decrement succeeds
and now we're back where we started, but the "success control" decrement trigger runs and moves onto the next part of the program. Everything is symmetrical between success and failure, so if the decrement had failed instead, the example would be the same but with success and failure state swapped.
Example programs
A Hello world program is available at Hello world program in esoteric languages (T-Z)#The Amnesiac From Minsk.
The Amnesiac From Minsk, level 2
Semantics
Level 2 works pretty similarly to level 1, with one big difference: instead of a decrement from 1 failing, it succeeds, decrementing the counter to 0. This is known as a "critical state" for the counter (in the sense that bad things can potentially happen very soon); if a counter that's currently at 0 is decremented again, you get undefined behaviour, a state which must be avoided in any valid program. The trigger in the = column has similar semantics as in level 1 – it runs on an attempt to decrement a counter at 1 – but is now called the "critical decrement" rather than "failed decrement" trigger (as the decrement didn't actually fail). (Fans of :≠ will be reminded of the way that that language works, in which you mustn't, say, attempt to disable a function that's already disabled. This language has quite a similar style.)
Syntax
The syntax for level 2 is entirely analogous for that at level 1; the semantic changes do not require any syntactic changes. The only difference is that the first line is
L2+=- rather than L1+=-.
Implementing level 1 in level 2
Making a similar change to a Minsky machine would be trivial; after a critical decrement, you could just increment the counter again then continue what you were doing. It turns out that it's possible to do something similar in The Amnesiac From Minsk (although the construction is a bit more complex due to the absence of an instruction pointer).
The idea is to emulate each level 1 counter with a triple of level 2 counters, called "value", "restore", and "increment". While the counter is not being accessed, "value" holds the same value as the level 1 counter being emulated would, and the other two hold 1. The triggers are connected as follows:
- "value" successful-decrement is the same as the emulated counter's successful-decrement trigger
- "value" critical-decrement increments "restore"
- "value" increment decrements "restore"
- "restore" successful-decrement is the same as the emulated counter's failed-decrement trigger
- "restore" critical-decrement increments "restore"
- "restore" increment decrements "increment"
- "increment" successful-decrement is the same as the emulated counter's increment trigger
- "increment" critical-decrement increments "increment"
- "increment" increment increments "value"
In order to emulate incrementing the counter, we increment "increment":
value restore increment x 1 1 Before starting the increment x 1 2 Increment starts from outside x+1 1 2 "value" incremented x+1 0 2 so it decrements "restore" x+1 1 2 which increments itself x+1 1 1 which decrements "increment"
and as that was a successful-decrement, we run the increment trigger, as desired.
To emulate decrementing the counter, we decrement "value". For a successful-decrement, this is trivial: it decrements successfully and the successful-decrement trigger runs. An emulated failed-decrement is more interesting:
value restore increment 1 1 1 Before starting the decrement 0 1 1 Decrement starts from outside 0 2 1 "restore" incremented 0 2 0 so it decrements "increment" 0 2 1 which increments itself 1 2 1 which increments "value" 1 1 1 which decrements "restore"
and now we're back where we started, continuing with the emulated failed-decrement trigger. Which is as we wanted.
Because The Amnesiac From Minsk is Turing complete at level 1, and we can compile level 1 into level 2, it's Turing complete at level 2 too.
Implementing level 2 in level 1
Going the other way is simpler, but not entirely trivial; incrementing a counter after a failed decrement leaves it in a different state from incrementing a counter after a critical decrement. The method we use is to construct signed counters out of pairs of unsigned counters; we have a "positive" and a "negative" counter, with triggers as follows:
- "positive" failed-decrement increments "negative"
- "negative" failed-decrement increments "positive"
- "positive" successful-decrement is the same as the emulated counter's successful-decrement trigger (because it runs on decrements from 2 or more to 1 or more)
- "negative" increment is the same as the emulated counter's critical-decrement trigger (because it runs on decrements from 1 or less to 0 or less)
- "positive" increment is the same as the emulated counter's increment trigger (and runs on increments from 1 or more to 2 or more)
- "negative" successful-decrement is the same as the emulated counter's increment trigger (and runs on increments from 0 or less to 1 or less)
The two counters effectively encode a single integer, whose value is (positive - negative) + 1, which gives all the behaviour that level 2 needs (while potentially useful for other purposes, too, as the "undefined" behaviour of decrementing a critical trigger is both well-defined and useful in this construction).
The Amnesiac From Minsk, level 3
Semantics
Unlike levels 1 and 2, in which only one counter is incremented or decremented at a time, a counter adjustment in the level 3 language affects two counters at once. Specifically, incrementing counter x decrements counter x+1, and a decrement cannot be made except via incrementing the previous counter. (The exception is incrementing the last counter; this doesn't cause a counter to be decremented.) The implementation starts running the program via incrementing the first counter, as before, but it now also has the side effect of decrementing the second counter. The first counter starts at 1, and can only go up from there (because there is no way to decrement it).
The language otherwise works like the level 2 language; decrementing a counter at 1 is a critical decrement, and that counter thus must not be decremented (and thus the previous counter must not be incremented) until the counter has been restored to a positive value. With the previous-level languages, this would cause problems, as two triggers would run as a result of the two changes. Level 3 does not use increment triggers, just decrement triggers; as a result, you get a successful-decrement or critical-decrement trigger running for the counter that was decremented. Again, the last counter is an exception, and does have an increment trigger, which runs when the last counter is incremented (as no counter is decremented in this case).
The I/O (well, output) extension explained above doesn't really work at this level. At present, there's no defined replacement for it, although perhaps one will be added at some point.
Syntax
Syntax is basically the same as with levels 1 and 2, but with the increment triggers removed, and with only the increment half of an adjustment shown (and the first line changed to L3=-):
L3 = - 1: +2; +1; @5 2: +0; +3; @9 This is a comment. 3: +1; +0; @12 +: +1
As can be seen, the last line starts with +: and has a single trigger specified, which is the increment trigger for the last counter. Note also that the first row is labeled 1:; the counter numbers still start at 0, but as counter 0 cannot be decremented, there's correspondingly no point in specifying decrement triggers for it.
Implementing level 3 in level 2
This is pretty trivial; you can use the same counters in level 2 as in level 3, and just have the increment trigger of each counter (but the last) decrement the following counter. As such, level 3 can be seen as a strict subset of level 2; it's level 2 with the additional constraint that all but the last increment trigger has to have a specified value.
Turing-completeness proof for level 3
The Amnesiac From Minsk level 3 is Turing complete. This proof proves this not via use of level 2, but rather by compiling programs from The Waterfall Model into it.
Each waterclock from The Waterfall Model is represented using the following, consecutively numbered, TAFM counters:
- a "padding counter" – this has an arbitrary value which is maintained to always be sufficiently large (i.e. it is not allowed to go near 0)
- some number of "decrement control counters", which normally have the value 1
- a "value counter", which holds the value of the waterclock
- some number of "increment control counters", which normally have the value 1
These are then concatenated to form the set of all counters (i.e. the last increment control counter of one waterclock is followed by the padding counter of the next waterclock). Counter 0 is the first padding counter, and its automatic starting value of 1 is sufficiently large (because it can never be decremented).
Control counters are chained together as follows: a critical decrement of a control counter causes that counter to immediately be incremented again (thus decrementing the next counter). On a successful decrement of a value counter, the corresponding padding counter is incremented (thus decrementing the first decrement control counter). On a successful decrement of a padding counter (which can't happen to the first waterclock's padding counter, only with subsequent waterclocks), the preceding waterclock's value counter is incremented; likewise, if the last counter is incremented, the last waterclock's value counter is incremented. This mechanism means that incrementing any of a waterclock's control counters will cause that waterclock to be incremented or decremented (depending on what sort of control counter it is), and in most cases restore the value of all the control counters to 1. Incrementing a waterclock will decrement the next waterclock's padding counter, and decrementing a waterclock will increase that waterclock's padding counter.
A successful (rather than critical) decrement of a control counter indicates that this is the counter that was incremented (in order to cause the increment or decrement of the waterclock). This effectively allows for sequencing of commands in a way similar to regular Minsky machines: to create a sequence of, e.g., "increment waterclock 2 twice then waterclock 3", you can choose a sequence of two increment control counters from waterclock 2 and one from waterclock 3, then cause the successful-decrement trigger of each counter in the sequence to increment the next counter in the sequence.
It then becomes easy to implement one instance of the steady decrement from The Waterfall Model: You just create a linked sequence of commands that decrements each waterclock in turn (the program starts here, as the first decrement is made to the second counter, which is a decrement control counter for the first waterclock). After this steady decrement comes a padding routine, which for each waterclock n in reverse order (i.e. starting with the highest-numbered), increments and decrements that waterclock kn times for some sufficiently large constant k. This has no net effect on the waterclock's value, but will increase the value of all the padding counters by k (because they're incremented kn times and then decremented k(n-1) times). Once the padding routine finishes, it returns to the start of the steady decrement routine, thus causing the decrement to be repeated forever for the lifetime of the program.
The one remaining case is implementing the zeroing triggers. This is done using the critical-decrement triggers of the value counters; these start a separate sequence of commands that increment waterclocks (i.e. the value counter's critical-decrement trigger is linked to an increment control counter, its successful-decrement trigger is linked to another increment control counter, and so on, until all the waterclocks have been increased by the appropriate amounts). The end of this chain increments the corresponding padding counter (just as the successful-decrement trigger of a value counter does), thus restoring things to the same state they would have been on a successful decrement (except for all the incrementation of the waterclocks' values in the meantime). Although a control counter will have the "wrong" value during this sequence (i.e. we aren't obeying the normal rule that control counters usually have the value 1), that control counter will necessarily be a decrement control counter, whereas only increment control counters are adjusted by this sequence, so the chain of increments will still work normally.
It is clear that there's a limit to how much the padding counters can shrink in each steady-decrement cycle (because each zeroing trigger will shrink each of them by at most some fixed finite amount), which means that it's always possible to choose k such that the padding counters will always have a net increase every cycle. Starting each padding counter at k will then ensure that the padding counters never zero. (As such, the critical-decrement triggers for padding counters are arbitrary and do not matter.)
The Amnesiac From Minsk, level 4
Semantics
Level 4 of The Amnesiac From Minsk is similar to level 3, but with different behaviour for the triggers, and a restriction on the counters as well. The restriction on the counters is that you may never have two critical counters in a row (attempting to create such a situation is undefined behaviour); as with level 3, the first counter always starts at 1 and can only go up from there (although the last counter can go down to 0). As for the triggers, each counter has but a single trigger; the result of the decrement determines which counter's trigger runs:
- If, in an increment/decrement pair, the decrement is critical, then the trigger for the decremented counter runs.
- Otherwise, the trigger for the incremented counter runs.
As an extra rule (that's part of the language definition, in order to make the language easier to implement, but which would nonetheless be obeyed by any useful program even if it didn't exist because otherwise some counters couldn't change both up and down), all the triggers that exist must be distinct (i.e. increment different counters).
Syntax
Syntax works as in previous levels, with the same sorts of changes; the first line is now L4?, and each line only lists one trigger. There are no longer special cases for the first and last lines. Thus, the language looks like this:
L4 ? 0: +2; @1 1: +0; @9 This is a comment. 2: +1; @12 3: +3; @5
Implementing level 4 in level 3
Just like implementing level 3 in level 2, this is trivial; you simply copy each of the triggers from the level 4 program into the two corresponding triggers in the level 3 program (apart from the first trigger, which has only one corresponding trigger (the successful-decrement trigger for the second counter) and thus only gets copied to one place).
It's currently unknown whether it's possible to go the other way, and implement level 3 in level 4.
Implementation in Last ReSort
To implement The Amnesiac From Minsk level 4 in Last ReSort, we first construct a list of integers from the list of counters by taking a cumulative sum of the initial values of the counters. So for example, if the initial values were (in order) 1, 7, 0, 4, 2, our cumulative sum would be 1, 8, 8, 12, 14. Then we permute the list according to the list of triggers; the element corresponding to the target of the trigger of the last counter comes first, the element corresponding to the target of the trigger of the penultimate counter counter comes second, and so on. The initial pointer points to the element that was permuted from the element corresponding to the first counter (which will always have the value 1).
Taking our example from above:
L4 ? 0: +2; @1 1: +0; @9 This is a comment. 2: +1; @12 3: +3; @5
we get a list [1, 10, 22, 27], which would then be reordered as [27, 10, 1, 22] to provide the Last ReSort program, with the initial pointer pointing to the third element.
In order to see how this construction works, consider what one Last ReSort step is doing, when interpreted through the lens of this construction:
- The increment is adding 1 to a single cumulative sum element. This corresponds to incrementing the accumulated element that was added at that point and decrementing the next element (which is exactly how memory changes in The Amnesiac From Minsk level 4).
- The retargeting is selecting an element. If the list of cumulative sums were strictly in order (i.e. we accumulated only positive values), then the element that would be selected is the nth from the end, if we incremented counter n (which is exactly the element that's the target of the decremented counter). The only way in which it can fail to be in strict order is if we decremented a counter down to 0, causing its cumulative sum to equal that of the counter afterwards and thus cause the pointer to point at the element before as a consequence of Last Resort's tiebreak rules (corresponding to using the target from the counter afterwards). Note that a three-way tie, which would cause problems, cannot happen because we disallow having two critical counters in a row.
In other words, the two languages are doing the same thing.