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
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>length(S).
Trace Example
| Program Evolution | i |
|---|---|
| +-++- (starting S) | N/A |
| +-++- (nothing exists leftward) | 1 |
| -++- | 2 |
| -++--+ | 3 |
| --+ | 4 |
| HALT (length(S)>3, 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 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 simplicities sake. It is defined as follows:
Let the length of x be denoted by |x|.
For n ∈ ℕ, 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 process 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 should be noted since p(n)=(number of executed steps)+1. If p(n) never halts for specific n, the output is 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 no longer decreasing at points. 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.