Convalescent is a two-instruction esolang based on a simple operation utilizing prime factors of integers, designed by Keymaker in 2024.
The language environment consists of the program, the memory manipulated by the program, and the accumulator, likewise manipulated by the program. The program is given as input. The memory is a list (whose order does not matter in implementations) of non-negative integers, initially with only one value, an instance of the smallest prime, 2. The accumulator is a register that can store any non-negative value, and is initially 0.
There are two types of instructions, ; and +. The program must contain at least one instruction. Instructions are executed sequentially, and after the last instruction is executed the instruction pointer returns to the first instruction (which is also where execution initially begins). If the memory becomes empty, the program halts.
; increases the accumulator by one.
+ causes the following effect (the implementation may do things differently as long as the effect is identical):
0 or 1 the program halts instead (with the memory and the accumulator remaining as they are). If not halted, continue to (2).1. Otherwise set accumulator to value 0. Then see if the memory is empty. If it is, halt, otherwise move to the next instruction.Here is a small table of examples of how the + instruction operates. On the table, 'memory before' means the state of the memory (a list of values) before the instruction is executed, 'prime factorization' is what the instruction factorized from the accumulator, and 'memory after' is what the state of the memory is after the completion of the instruction's execution. 'accumulator after' is what the accumulator is set to. 'comment' is a brief textual explanation.
| memory before | prime factorization | memory after | accumulator after | comment |
| 3, 5, 5 | 7, 7 | 3, 5, 5 | 0 | nothing was altered because nothing in prime factorization existed in memory |
| 2 | 2, 19, 173 | 19, 173 | 1 | at least one number from the factorization (2) exists in the memory at least once, so instruction will alter memory. an instance of 2 is removed from memory, and n-1 added (1-1=0, thus none). neither 19 or 173 exists in memory, so all instances of both (there is one of each) are added to memory |
| 3, 5, 5 | 5, 223 | 3, 5, 223 | 1 | 5 exists twice in memory, one copy is removed, n-1 (1-1=0) added. 223 not in memory, so all instances of it (one in this case) are added |
| 3, 5, 5 | 5, 5, 5 | 3, 5, 5, 5 | 1 | 5 exists twice in memory; one copy is removed, n-1 (3-1=2) added |
| 3, 7, 11, 11 | 7, 11, 23, 23 | 3, 11, 23, 23 | 1 | because at least one value in prime factorization exists in memory (7 once, 11 twice), instruction proceeds; remove one instance of 7 from memory, add 0 instances. remove one instance of 11, add n-1 (1-1=0). no instances of 23 in memory, so add all instances of 23 in prime factorization (two) |
| 43 | 43 | (empty) | 1 | 43 exists once in memory, one copy is removed, n-1 (1-1=0) added. memory becomes empty; program halts after the instruction. |
When reading in the program, all characters other than ; and + are ignored.
An example program that does not do anything useful (generated using the MM translator, changed into the simple format, and arranged into rectangular shape; it is a translation for 1 dec A 1 1):
;;;;+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;+;;+;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;;;;;;;;;;;; ;;;;;;+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;+;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;+;;+
Because programs can and will easily become too large to store and execute, it is advised that the interpreter allow for this alternative format. The Minsky Machine translator outputs in this format.
(1035)+;;+(818277720)+
It supports ; and + normally, but if encountering a decimal number (positive, non-zero) inside parentheses, it is taken to represent that number of ; instructions.
The language is Turing-complete, shown via Minsky Machine translation.
A unique prime number is assigned for each MM register and instruction. There are also two additional primes used for (1) control flow within instructions (this prime will be reqularly removed and added back) and (2) determining whether the program is running (which will be removed during a halting instruction).
The technique I developed for the proof is such that for most steps (a combination of increasing the accumulator and executing it) within an instruction simulation, there is an alternative number that is meant to have no effect at all. Thus, everywhere where executing a number that is one smaller or one larger than the one that is designed to have effect (that is, removing numbers or adding them, setting the accumulator to 0 or 1), that number must not contain factors used elsewhere. Otherwise it might, for example, remove an instance of a register's data, or activate a wrong instruction by adding data.
For example, the intended prime factorization to execute (by +) might be (7, 11, 13), from number 1001. However, if the value 1002 is executed instead, it has factors (2, 3, 167). Now, it might happen that 167 is a prime associated with a register. Executing 1002, 167 might be found, and one instance of it be removed, thus destabilizing the program simulation.
My solution to prevent clashes (which is what I call it when the unintentionally executed number contains in its factors primes reserved for the program) is to let the translator do some number-crunching. It checks that every step (or rather, only the steps that need to be safe, which is most of them) of every instruction is safe, and if a potentially clashing number is found, the prime is replaced with a larger prime. That may yield a new clash, so the operation is done again. For as many times until eventually there will be a program that has no clashing.
My algorithm is very simple; if a number in the non-sense numbers (the -1 or +1 numbers whose factorizations are not meant to have any effect) clashes with a reserved prime, that particular prime is rewritten with a new prime that will be the largest in the program, and this process is repeated as long as it needs to be. It is much improvement to my first, even simpler, version: it just shifted all numbers by a prime and tried again. The earlier version managed a test program in about two hours, which the improved second version solves in a couple of minutes. A larger test program the earlier could not solve in several hours, whereas the new did in half an hour or so. Granted, that is a terrible time, too.
Improving the translation calculations could likely be done by choosing large primes far from each other, but I have not investigated whether it is actually so. Probably adding more randomness to getting a new prime (instead of taking the next largest prime) might help too. It surprised me how many times clashing actually happens. There might also be some basic property of primes that I do not know but which might make the translation time/computational effort more or less instantaneous (without any clashing) if the right primes are used. Even writing the translator in clumsy C instead of Python would probably reduce the running time to a tenth of itself, at the very least.
As for how the actual instructions INC, DEC, and HALT are implemented in Convalescent, see my internal design document lang.txt. It may not be the clearest and there may be typos and inaccuracies (it was, as said, for my own use only). For instance, it uses 91 for a prime (it is not one) because I could not be bothered to check whether it is one or not. But it does not matter for delivering the idea, as long as the reader pretends it is correct. Likewise, it uses + and . for ; and + because I had not yet chosen the final characters.
convalescent.py - A somewhat verbose interpreter written in Python.
mmtoconvalescent.py - A Minsky Machine into Convalescent translator. Prints a lot of stuff, eventually at the end an empty line and then the translation.
-- Keymaker, 17.12.2024