Afterstar is a minimal esolang based on deterministic division and program-defined multiplication of a single unbounded memory value, designed by Keymaker in 2024.
The language operates on an array of integers (containing at least one integer), given as the program. Each integer has its unchancing position and an index (starting at 1 for the first integer and growing by one for each successive integer). There is the index pointer, which points to an integer (initially to the first in the array).
The memory is an unbounded non-negative integer. Initially its value is the smallest prime number, 2. If the memory ever becomes 0, the program will halt (successfully).
One step of execution consists of first checking if the memory is 0, and halting if it is. If not zero, then the instruction pointer attempts to divide the memory with its current value (not by the value in the array it is pointing to, but its own current value), and if the memory is dividable by the instruction pointer (so that the remainder is zero), then it is divided by it. After dividing (if it succeeded), the memory is multiplied by the integer stored in the array, the integer the index pointer points to. Afterwards, whether anything was done or not, the index pointer is increased by one, unless it is already pointing to the last integer, in which case the index pointer is set to 1 and thus points to the first integer again.
There have been languages that divide and multiply integers, most famously perhaps Minsky's variation of the counter machine with divide and multiply instructions instead. An aspect that is crucially different in Afterstar is that none of the dividing values can be defined as such, and there are no states or control flow. Only the multiplications are defined. Dividing is deterministically attempted with every index value (from 1 to the number of defined integers), cyclically and eternally (unless the program halts).
As the system was designed to be simple to read and execute, programs are given in this simple format: ( presents the integer in unary (zero instances for value zero), followed by * to indicate the end of the integer. All other characters are ignored. An interpreter needs to consider itself only with valid programs. An example program:
(* ((* (((* ((((((((((* (((((* * (((((((*
The program is somewhat senseless, only made to showcase the format. For most integers, it simply repairs the potentially unwelcome effect of dividing the memory when it is not meant to be divided; if dividing happens, it multiplies the memory by a value that equals the index value of those integers. The fourth integer is different. If, when executing that integer, the memory is dividable by 4, it will be divided by 4, and then multiplied by 10. When executing the sixth integer, if the memory is dividable by 6, it is divided by 6, then multiplied by 0, and thus causing the program to halt (at the beginning of the next instruction, where zeroness of the memory is inspected). The seventh and last integer defines seven, which is rather pointless at the end of a program, but can be done.
Because most programs grow uncontainable rather fast, there is an alternative format that an interpreter should support (if it aims to be practical, that is, capable of running actual programs). In this format, each line that is not an empty line has two non-negative decimal numbers, separated by the three characters :*:. The numbers on the left must be in increasing order and larger than 0. The numbers on the right may be any non-negative integer and of course need no ordering. An integer not defined in the program (in this format) is automatically defined being equal to its index value. The array is as long as the largest defined index location. Example:
2:*:2409847 341:*:2015 403:*:2635 527:*:93 555:*:703 573:*:5539 589:*:4991 713:*:3689 899:*:0
Storing this simple 6-instruction MM program translated into Afterstar would require more than two million bytes of harddrive space. While that is relatively little for modern machines, a slightly larger program will easily require millions of terabytes.
Below is the simplest MM program that does not halt (1 inc A 1) translated into Afterstar using my translation program, using the simple format.
(* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((* ((((* (((((* ((((((* (((((((* ((((((((* (((((((((* ((((((((((* (((((((((((* ((((((((((((* (((((((((((((* ((((((((((((((* (((((((((((((((* ((((((((((((((((* (((((((((((((((((* ((((((((((((((((((* (((((((((((((((((((* ((((((((((((((((((((* (((((((((((((((((((((* ((((((((((((((((((((((* (((((((((((((((((((((((* ((((((((((((((((((((((((* (((((((((((((((((((((((((* ((((((((((((((((((((((((((* (((((((((((((((((((((((((((* ((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* ((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((* (((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((*
The language is Turing-complete, as is shown via Minsky Machine translation.
The translated program uses prime numbers. The one-integer memory is a multiple of primes. Primes are added by multiplying the memory with numbers that are multiples of primes and removed by dividing the memory with numbers that are multiples of primes. Interestingly, the language itself has no concept of prime factorization, or even of primes themselves; it all happens simply by multiplying and dividing with the right numbers.
Since there is no way to define what to divide by, the multiplication parts must be placed at specific locations. A problem immediately arises if there is (and there will be) a need to divide by an identical number at two places. This is solved with what I call locative primes in the context of this proof.
Each MM instruction is translated into one (inc, halt) or three (dec) Afterstar commands (in other words, integers defined at specific indexes). The translator utilizes locative primes to place the numbers in a growing order and to enable dividing by an already-used number in the first place.
The system of locative primes is simple. Each subsequent unit of the translation (an integer for multiplication) is placed into location that is an arbitrary number (which is at least one) onwards from the previous index (and the first placement is at index 2, which is used by the initialization). The distance does not matter, but of course for execution times it is the better the less there is for the index pointer to travel. Because of the locative primes, the actual primes used for the MM instruction simulation can be placed as many times as needed, in any sequence wanted. There is the 'first free prime' which indicates the first prime that can be used as a locative prime. Primes 2 and 3 are reserved, then the next primes for every register, then primes for every instruction. After them, the locative primes. The same locative prime can be used by multiple integers. Whenever a locative prime is removed while dividing, it is returned right after in the multiplication. An instance of all locative primes used by the program exists at all times so that they may be readily used by any integer. (The translation never uses more than one locative prime to place an integer. Whereas multiplying smaller ones in favour of larger ones would result in more optimized placement of integers, it did not occur to me while I was designing the translation and doing the programming. And because there is no need to complicate this further, I did not start doing so later.)
Listed below are the translations of MM instructions in a sort of abstract format where the left side is what divides the memory and the right side is what the memory is subsequently multiplied by (if it can be divided first).
For INC the translation is inst1 : regA inst2, where inst1 is the instruction, regA the register to increase, inst2 the next instruction. If the instruction prime is found, it is removed, and an instance of the register is added, and an instance of the next instruction.
For DEC the translation is three integers. instA : temp, where instA is the instruction, temp is the temporary register (always associated with prime 3). If instA is found, it is removed and an instance of the temporary register is added. That is followed by regA temp : instB, where regA is the register to decrease and temp is the temporary register, instB is the next instruction in case the decreasing operation succeeds (that is, the register is non-zero). If both the register and the temporary register exist, it means the register can be divided, and the success state placed into memory. The third instruction, temp : instC, where temp is the temporary register and instC the next instruction in case the decreasing operation fails (which it has done, if this part is executed). This part is executed if temp exists (meaning it was not removed in the second part), meaning the decreasing has failed, and so the instruction associated with the failure will be activated.
For HALT the translation is inst1 : 0, where inst1 is the instruction, and 0 the value zero. The associated instruction is removed, and the memory is multiplied by 0. The program halts at the beginning of the next step, when it is seen if the memory is zero or not. (And thus the simulated MM halts, too.)
The program initialization happens at index 2. As the memory is always 2 when an Afterstar program begins, the index pointer divides the memory at index 2, and removes the 2 (which is never added back), and multiplies the memory (which is 1 at that point) with a value that is the prime associated with the first instruction multiplied by every locative prime used in the program.
afterstar.py - An interpreter written in Python.
mmtoafterstar.py - Minsky Machine into Afterstar translator. Give an additional argument (can be anything) for printing the program in the simple and space-consuming format. Regardless of the output format, the translator will output data about the program, then an empty line followed by the actual translation.
-- Keymaker, 17.12.2024