View source for 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|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 ==
{| class="wikitable"
|+
executes 4 instructions and halts at index i = 5
!Program Evolution
!i
|-
| +-++- (starting S)
|N/A
|-
| +-++- (nothing exists leftward)
|1
|-
| -++- 
|2
|-
| -++--+
|3
|-
| --+
|4
|-
|<nowiki>Halt (|S| = 3, i = 5 > 3).</nowiki>
|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 length(x) = |x|. 

For n ∈ ℕ<sub>>0</sub>, 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. Otherwise, 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.

[[Category:Functions]]