PLUSMINUS
PLUSMINUS is an esoteric programming language developed by Discord user Jack in 2026. It is a “string-based copy-automaton” that has only 2 commands, similar to its inspiration XigXag, an esoteric language developed in 2001 by Chris Pressey. Despite its extreme simplicity, its Turing Completeness is actually unknown.
Definition
Let |x|=length(x). For a non-empty finite string S under the binary alphabet {+,-}, on step i=(1,2,…)
- If the i-th symbol is +, copy the first i-1 symbols and append them to the end.
- If the i-th symbol is -, delete the first i-1 symbols.
i never resets and advances each time. HALT when i>|S|.
Trace Example
| Program Evolution | i |
|---|---|
| +-++- (starting S) | N/A |
| +-++- (nothing exists leftward) | 1 |
| -++- | 2 |
| -++--+ | 3 |
| --+ | 4 |
| Halt (|S|=3, i=5>3). | 5 |
Halting characteristics for these programs include the following:
- The singular + halts
- ++…++ (with at least 2 +’s) never halts
- The program consisting of only - always halts for any length.
Known Halting Time Champions
Below are PLUSMINUS programs of initial strings of size 1–16 and their corresponding number of “steps” until halting:
+=1
-+=3
-++=4
-+++=7
++++-=15
+++-++=18
++++---=20
--++++++=32
++++-+--+=44
+++++-+-+-=196
+++++-+--+-=913
+++-++++++-+=5940
+-++++++--++-=728
++++-++++++---=608
-+-++++++---+++=2582
+++++-++++-+-++-=31441
Relation to BB(n)
We can concisely define 2 functions that both include the definition of PLUSMINUS in their definition using just over 300 characters. This version uses 1 and 0 instead of + and - for simplicity. It is defined as follows:
Let the length of x be denoted by |x|.
For n ∈ ℕ>0, convert n to its binary form B. Assuming i=(1,2,…):
If its i-th symbol is 1, copy its first i-1 symbols and append them to the end. If else, delete its first i-1 symbols.
i never resets and advances each time. Halt when i>|B|.
- p(n)=min(i) such that i>|B| (or 0 if the run never halts)
- P(n)=max(p(k)) for k=(1,…,n)
Explanation
The list of champions above details executed steps, while p(n) returns the instruction index when halting is detected. It is a minor difference, but it should be noted since p(n)=(number of executed steps)+1. If the PLUSMINUS run starting from the binary representation of n never halts, define p(n)=0. Halting in PLUSMINUS has not been proven undecidable/decidable. Also, ordinary binary integers never start with 0, so P(n) actually excludes all programs that begin as such.
Essentially, P(n) takes the “running maximum” of p(n), so it is non-decreasing. Out of the first 1000 inputs, 49 were unresolved under a limit of 10000 executed instructions or 2 million bits of string storage. Said computation has established that P(1000)≥134. From the halting times section, the PLUSMINUS program “+++++-++++-+-++-“ corresponds to “1111101111010110” which is “64470” in decimal. It takes 31441 “steps” to halt. Therefore p(64470)=31442 (remembering the “+1” as per p(n)’s definition) and hence P(64470)≥31442.