PLUSMINUS - Revision history

Polygon: Linked Turing completeness

2026-10-30T21:17:55Z

Linked Turing completeness

← Older revision		Revision as of 21:17, 30 October 2026
Line 1:		Line 1:
	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.		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 ==		== Definition ==

Polygon: Spacing for better readability

2026-10-30T20:43:31Z

Spacing for better readability

← Older revision		Revision as of 20:43, 30 October 2026
Line 80:		Line 80:
	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:'''		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\|.		Let length(x) = \|x\|.

	For n ∈ ℕ<sub>>0</sub>, convert n to its binary form B. Assuming i=(1,2,…):		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.		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\|.		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) = min(i) such that i > \|B\| (or 0 if the run never halts)

	* P(n)=max(p(k)) for k=(1,…,n)		* P(n) = max(p(k)) for k = (1, …, n)

	== Explanation ==		== 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.		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~~.		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]]		[[Category:Functions]]

Polygon: /* Trace Example */ even more spacing

2026-10-30T20:40:28Z

Trace Example: even more spacing

← Older revision		Revision as of 20:40, 30 October 2026
Line 13:		Line 13:
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+
	executes 4 instructions and halts at index i=5		executes 4 instructions and halts at index i = 5
	!Program Evolution		!Program Evolution
	!i		!i
Line 32:		Line 32:
	\|4		\|4
	\|-		\|-
	\|<nowiki>Halt (\|S\|=3, i=5>3).</nowiki>		\|<nowiki>Halt (\|S\| = 3, i = 5 > 3).</nowiki>
	\|5		\|5
	\|}		\|}

Polygon: /* Definition */ more spacing

2026-10-30T20:39:48Z

Definition: more spacing

← Older revision		Revision as of 20:39, 30 October 2026
Line 8:		Line 8:
	* If the i-th symbol is -, delete the first i - 1 symbols.		* If the i-th symbol is -, delete the first i - 1 symbols.

	i never resets and advances each time. '''''HALT''''' when i>\|S\|.		i never resets and advances each time. '''''HALT''''' when i > \|S\|.

	== Trace Example ==		== Trace Example ==

Polygon: /* Definition */ spacing

2026-10-30T20:39:33Z

Definition: spacing

← Older revision		Revision as of 20:39, 30 October 2026
Line 2:		Line 2:

	== Definition ==		== Definition ==
	Let \|x\|=length(x). For a non-empty finite string S under the binary alphabet {+,-}, on step i=(1,2,…)		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 +, copy the first i - 1 symbols and append them to the end.

	* If the i-th symbol is -, delete the first i-1 symbols.		* If the i-th symbol is -, delete the first i - 1 symbols.

	i never resets and advances each time. '''''HALT''''' when i>\|S\|.		i never resets and advances each time. '''''HALT''''' when i>\|S\|.

Polygon: /* Known Halting Time Champions */ spacing

2026-10-30T17:56:11Z

Known Halting Time Champions: spacing

← Older revision		Revision as of 17:56, 30 October 2026
Line 45:		Line 45:
	Below are PLUSMINUS programs of initial strings of size 1–16 and their corresponding number of “steps” until halting:		Below are PLUSMINUS programs of initial strings of size 1–16 and their corresponding number of “steps” until halting:

	+=1		+ = 1

	-+=3		-+ = 3

	-++=4		-++ = 4

	-+++=7		-+++ = 7

	++++-=15		++++- = 15

	+++-++=18		+++-++ = 18

	++++---=20		++++--- = 20

	--++++++=32		--++++++ = 32

	++++-+--+=44		++++-+--+ = 44

	+++++-+-+-=196		+++++-+-+- = 196

	+++++-+--+-=913		+++++-+--+- = 913

	+++-++++++-+=5940		+++-++++++-+ = 5940

	+-++++++--++-=728		+-++++++--++- = 728

	++++-++++++---=608		++++-++++++--- = 608

	-+-++++++---+++=2582		-+-++++++---+++ = 2582

	+++++-++++-+-++-=31441		+++++-++++-+-++- = 31441

	== Relation to BB(n) ==		== Relation to BB(n) ==

Polygon: Added Category:Functions

2026-10-30T17:24:55Z

Added Category:Functions

← Older revision		Revision as of 17:24, 30 October 2026
Line 96:		Line 96:

	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.		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]]

JackM1945: /* Relation to BB(n) */ made it clearer

2026-10-29T20:30:56Z

Relation to BB(n): made it clearer

← Older revision		Revision as of 20:30, 29 October 2026
Line 84:		Line 84:
	For n ∈ ℕ<sub>>0</sub>, convert n to its binary form B. Assuming i=(1,2,…):		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. ~~If else~~, delete its first i-1 symbols.		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\|.		i never resets and advances each time. Halt when i>\|B\|.

JackM1945: /* Explanation */ more errors fixed

2026-10-29T20:21:00Z

Explanation: more errors fixed

← Older revision		Revision as of 20:21, 29 October 2026
Line 80:		Line 80:
	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:'''		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\|.		Let length(x)=\|x\|.

	For n ∈ ℕ<sub>>0</sub>, convert n to its binary form B. Assuming i=(1,2,…):		For n ∈ ℕ<sub>>0</sub>, convert n to its binary form B. Assuming i=(1,2,…):

JackM1945: Fixed grammar stuff

2026-10-29T20:20:09Z

Fixed grammar stuff

← Older revision		Revision as of 20:20, 29 October 2026
Line 2:		Line 2:

	== Definition ==		== Definition ==
	For a non-empty finite string S under the binary alphabet {+,-}, on step i=(1,2,…)		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 +, copy the first i-1 symbols and append them to the end.
Line 8:		Line 8:
	* If the i-th symbol is -, delete the first i-1 symbols.		* If the i-th symbol is -, delete the first i-1 symbols.

	i never resets and advances each time. '''''HALT''''' when i>~~length(~~S).		i never resets and advances each time. '''''HALT''''' when i>\|S\|.

	== Trace Example ==		== Trace Example ==
	{\| class="wikitable"		{\| class="wikitable"
	\|+~~+-++- takes~~ 5 ~~steps to halt~~		\|+
			executes 4 instructions and halts at index i=5
	!Program Evolution		!Program Evolution
	!i		!i
Line 31:		Line 32:
	\|4		\|4
	\|-		\|-
	\|~~HALT (length~~(S)>3, 5>3)		\|<nowiki>Halt (\|S\|=3, i=5>3).</nowiki>
	\|5		\|5
	\|}		\|}
Line 42:		Line 43:

	== Known Halting Time Champions ==		== Known Halting Time Champions ==
	Below are PLUSMINUS programs and their corresponding number of “steps” until halting:		Below are PLUSMINUS programs of initial strings of size 1–16 and their corresponding number of “steps” until halting:

	+=1		+=1
Line 77:		Line 78:

	== Relation to BB(n) ==		== 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:'''		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\|.		Let the length of x be denoted by \|x\|.
Line 87:		Line 88:
	i never resets and advances each time. Halt when i>\|B\|.		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 ~~for said n~~)		* p(n)=min(i) such that i>\|B\| (or 0 if the run never halts)

	* P(n)=max(p(k)) for k=(1,…,n)		* P(n)=max(p(k)) for k=(1,…,n)

	== Explanation ==		== 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 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.		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 ~~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.		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.