Autopsy is a minimal esoteric programming language designed in 2018. It has 2 instructions and 4 unbound registers.
The program is a finite string of . and ; instructions. When reading the program file, all other characters are ignored. The program must be at least 1 instruction long.
There are 4 unbound registers (a, b, c, d), of which the first (a) is initially chosen. The registers are initially 0, which is also their minimum value. They have no upper bound.
The program execution is begun with the instruction pointer pointing at the first instruction. After each instruction, the instruction pointer moves forward either 2 or 3 times. If during a move the instruction pointer moves past the last instruction, it is located to the very first instruction (thus, for instance, if the instruction pointer is at the last instruction and is moved 3 times forward, it ends up to the third instruction (assuming the program itself is at least 3 instructions long)). The program never halts.
An instruction is executed thus:
., increase the current register's value by 1, then move the instruction pointer forward 2 times. Done.;, see the value of the currently chosen register. If the register's value is 0, move the instruction pointer forward 3 times. If the register's value is larger than 0, decrease the register's value by 1, then move the instruction pointer forward 2 times. Last, no matter what the value of the register was, when executing ;, the next register is chosen afterwards. If the focus is currently on the last register (d), the focus moves to the first (a). Done.Below is a simple 10-instruction example program that repeats infinitely this simple task: 1. Switch to next register twice. 2. Increase the current register's value.
..;...;...
Below is the program in a table. The numbers above . and ; are just the locations of the instructions within the program. In this case, only the even instructions (shown in bold) are ever executed. The instructions that are not executed are all . here, but they could be randomly . or ;, it does not matter since they are never executed, all that matters is that they are actual Autopsy instructions used in forming the program's structure.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
. | . | ; | . | . | . | ; | . | . | . |
Below is a tracing of the example program starting and running until the instruction pointer is in the first instruction (location 0) again.
(0) . [0] 0 0 0 -> (2) [1] 0 0 0 (2) ; [1] 0 0 0 -> (4) 0 [0] 0 0 (4) . 0 [0] 0 0 -> (6) 0 [1] 0 0 (6) ; 0 [1] 0 0 -> (8) 0 0 [0] 0 (8) . 0 0 [0] 0 -> (0) 0 0 [1] 0
Each row shows the location of the instruction pointer, what instruction is being executed, the states of the registers. After the arrow is shown the effects of the instruction's execution; the new location of the instruction pointer and what is now the new, current state of the memory.
As one can see, at the end of this trace the instruction pointer is back at location 0 but the currently chosen register is c, the third register. During the new, similar cycle the program will proceed to choose the a-register and increase it.
The Turing-completeness of Autopsy can be shown via Minsky Machine translation.
The notation used here is something I designed as a mental aid, and it was quite necessary for me when I was designing the translation method. In fact, the translator program itself internally creates the translation in such format before converting it into actual Autopsy code. If running the translator with an extra argument (such as "abc"), the translator outputs this middle phase data instead.
a b c d a b
+ - - + - + - + - + + + -
. . . + + + - + + - + + -
c d a
Above is an example of the notation (the program itself is meaningless). The lines with letters are just a reading aid for seeing which register the instruction is accessing (note: the translator does not produce them). + stand for . instructions, - for ; instructions, other characters mark instructions that will never be executed, and will be replaced by . instructions in the final output. (Why + and - are used to represent . and ; in this notation is simply because of their better legibility.) Even though Autopsy is 1-dimensional and the instruction pointer simply moves either 2 or 3 instructions forward, it is possible to think of the program space as if it had two levels and where changing the level happens with a ; when the current register's value is 0. So, in this notation, the upper level has the even-numbered instructions 0, 2, 4, and so on, and the lower level the odd-numbered 1, 3, 5, and so on. In a more compact 1-line form the above example program would be:
+.-.-.++-+++--++-++-++++--
Which can be changed into its final Autopsy form with simple character substitution (+ into ., - into ;, all others into . (although in this case they are . already)):
..;.;...;...;;..;..;....;;
The idea of the MM-to-Autopsy translation is to translate the given Minsky Machine program into components that are placed back to back on these two levels. The input program is any Minsky Machine program using no more than 2 registers and only INC and DEC instructions (which is, of course, a Turing-complete system). The instruction labels should be sequential numbers beginning from 1: 1, 2, 3, and so forth.
The Autopsy program uses the 4 registers in the following way: the a-register is for indicating which simulated MM instruction is to be executed, the b-register is the first MM register, the c-register is the second MM register, and the d-register is used for the control flow on the Autopsy-level of the program.
The translated program works the following way: Each component (a simulation of MM instruction, in other words) first decreases the a-register. In case the a-register is 0, the simulated instruction is executed, otherwise the control flow is moved forward, and the same testing is done with the next component. At some point the a-register will be 0 and an instruction is executed, during which the a-register is set to a new value. The values used are relative to the location of the component that sets them and its target component; for example, if the a-register is set to 1, that means that the component that is to be executed is not the next but the one after that. The execution (or potential execution) of components wraps from last to first in a natural way when the Autopsy instruction pointer moves to the beginning at the end of the program.
Here is the INC component (in this example, increasing the b-register (first MM register) and setting the a-register to 2):
a b c d a b c d - + - + - + - + - + - + - + + + + - . + - + - + - + + + - + + - + - - . b c d a b c d
The execution of it begins with decreasing the a-register. If it is 0, it cannot be decreased, and the instruction pointer moves forward 3 times, which, using this notation, means jumping to first + of the lower level. There, to get the chosen register back to a, registers b and c and d are each increased and decreased, thus keeping their values intact but changing the register focus. Eventually the a-register is chosen and it will be increased 2 times (an INC instruction that is executed is always successful, so the a-register is set to the INC instruction's success-target), then another increase-decrease to switch the focus to the b-register, which will be increased by 1, then it and the c-register are increase-decreased to switch focus to the d-register. To switch back to the upper level, the d-register is decreased. At this point, the d-register always needs to be 0 so that the instruction pointer is moved 3 times instead of 2. The instruction pointer thus moves back to the upper level (in a manner of speaking) and to the beginning instruction of the next component. If, alternatively, the first decreasing of the a-register happens, the instruction pointer moves along the upper level, switching registers, until near the end increasing the d-register a few times. This is to position the levels so that the control flow returning from the lower level is aligned with the upper level so that the register focus is focused on the a-register after either route is done. In the beginning of every component, the chosen register is a.
What about the d-register? As one may notice, executing the upper route in this case leaves the d-register with value 3, whereas executing the lower route leaves it with value 0. That would cause problems later were there not the component called d-decreaser:
a b c d a b c d
+ - + - + - - + - + - + - + -
. . . . . . . + - + - + - - .
a b c d
Each INC component is followed by as many d-decreasors as is needed to reset the d-register to 0, if executing the upper route leaves it larger than 0. In this example case, because the d-register is potentially left to 3, there would be 3 d-decreasers after the INC component. The workings of the d-decreaser are simple. First the register focus is moved to the d-register, which is decreased. If the d-register is 0, the instruction pointer moves 3 forward, to the first + of the lower level (figuratively speaking). The registers are switched until focus is on the d-register again, which is then decreased, and the control flow returns to the upper level and the first instruction of the next component. If the upper route were executed, there would be nothing but switching the registers, and the d-register would be 1 lesser after executing the component because of the decreasing happening in its beginning. Whichever route is taken, the register focus is back at the a-register after the component is executed.
DEC register is not much more complicated than INC:
a b c d a b c d
- + - + - + + - + - + - + - + + + + + + + + + -
. + - + - + - + + - - + - + - + + - + - + - - .
b c d a b c d a b c d
^fai ^dec ^suc
As in case of INC, first the a-register is decreased to see if the current component is to be executed. If the a-register is 0, the instruction simulation is executed, and the control flow moves forward 3 and to the first + of the lower level. Registers are increased and decreased to switch them without changing their value, until the a-register is chosen. It is, in this case, increased by 1 to set it to 1 (not counting the increase-decrease operation that switches the focus to b). Setting this is anologous to setting the a-register to direct to the failure-target of the DEC instruction. Next, b (the first MM register) is decreased (in this case; alternatively it is the next the c-register that is decreased). If the b-register is 0, the control flow moves 3 forward (to the upper level), otherwise the register is indeed successfully decreased, and the simulated DEC instruction is a success, so the execution continues on the lower level and after switching register focus back to the a-register, the a-register's value is manipulated so that the register will now guide the execution to the component that is determined by the success-target of the DEC instruction. After that, registers are switched until the d-register is chosen, which is decreased. Since it is always 0 at this point, the control flow moves to the upper level and to the first instruction of the next component. Alternatively, if the first the a-register were larger than 0 and the upper level were executed (or if decreasing the b-register returned the instruction pointer up), the d-register would be left larger than 0. In this case, the worst-case scenario, so to speak, is the d-register being 9 (1+8), so this DEC simulation would be followed by 9 d-decreasers exactly the same way an INC would be.
That is all there is to this particular translation method. Here is an example Minsky Machine program (6 instructions):
1 inc A 2 2 inc A 3 3 inc A 4 4 dec A 5 6 5 inc B 4 6 dec A 6 6
And its resulting Autopsy translation (1236 instructions):
;...;;..;;..;;..;;..;..;;..;.;;...;...;...;.;...;;..;;..;;.;;.;...;;..;;..;;..;; ..;..;;..;.;;...;...;...;.;...;;..;;..;;.;;.;...;;..;;..;;..;;..;..;;..;.;;...;. ..;...;.;...;;..;;..;;.;;.;...;;..;;...;;...;;.;;..;;..;.............;...;...;.; ;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;; ..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;. ..;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.; ;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;; ..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;.;...;;.. ;;..;;..;...;...;;...;.....;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;; ..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;. ..;.;...;;..;;..;;.;;.;...;;..;;...;........;...;;.;;..;;..;...;...;...;.;;...;. ..;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;.. ;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;. ..;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;. ..;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;..;;.;;...;...;...;.;...;;..;;.. ;;.;;...;...;...;.;...;;..;;..;;.;;.
autopsy.py - An interpreter written in Python. Provides debug of the memory state and the instruction pointer location before the current instruction is executed.
mmtoautopsy.py - Translates the given Minsky Machine program into Autopsy. If given an extra argument (like "abc") it outputs translation in the middle format.
-- Keymaker, 5th December 2018