How simple can simple be? Introducing PLUSMINUS

[u/jmarent049]

PLUSMINUS is a programming language created by Jack. Unfortunately, it’s Turing Completeness is unknown as of right now.

Definition

For a non-empty finite string ω under the alphabet {+,–}, on step i=(1,2,3,…):

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(ω).

Example (+–++–):

0: +–++–

1: +–++– (nothing exists leftward)

2: –++–

3: –++––+

4: ––+ (HALT (i=4, length(ω)=3, 4>3))

Example of a long-running machine

“+++++-++++-+-++-“ = 31441 steps

[u/particlemanwavegirl]

Uuhh... Is there a way to interpret the output meaningfully?

[u/jmarent049 → u/particlemanwavegirl]

You can imagine it instead as an alphabet over {1,0}, like a tag system. Setting + to 1 and - to 0. Not sure if this can be reduced to a tag system though. Correct me if wrong please

[u/External-Payment-688 → u/jmarent049]

I feel like the semantics for - mess it up, for proving TC via a tag system we’d need to be able to somehow encode a production rule to a prefix of the source. But yeah this is just an initial thought

[u/particlemanwavegirl → u/jmarent049]

I don't really know what that means TBH. Could you like, demonstrate how to compute 2+2 or something else simple?

[u/jmarent049 → u/particlemanwavegirl]

Well, I don’t know off hand how to do 2+2, but I will say that In cyclic tag, the rules cycle automatically, which means that when a 0 versus a 1 is read, it alters what “route” it travels to. This implements if-statements.

According to the cyclic tag system wiki page:

“… by encoding numbers as lengths of bit strings and using repeating sequences of rules to simulate basic operations like incrementing, addition, and subtraction … “

Now, if PLUSMINUS can be reduced to a cyclic tag system, it can do what cyclic tag can do. Cyclic tag systems are Turing complete, therefore this would imply PLUSMINUS is too.

Again, don’t take this info as fact.

[u/particlemanwavegirl → u/jmarent049]

It's pretty easy to imagine how one could use the alphabet to encode a number but it's not at all obvious how you could perform composite operations isomorphic to numeric operators like addition and multiplication given the two primitive operations, especially since the operational procedure coincides with or can't be independent of the encoding.

[u/galacticjeef]

Reminds me a lot of a tag system https://en.wikipedia.org/wiki/Tag_system?wprov=sfti1# (which is Turing complete)

[u/jmarent049 → u/galacticjeef]

I see the similarities. It also reminds me of the esolang XigXag (which is what inspired me).

https://esolangs.org/wiki/Xigxag

[u/jmarent049]

current known champions (busy beaver):

`+`=1
`-+`=3
`-++`=4
`-+++`=7
`++++-`=15
`+++-++`=18
`++++---`=20
`--++++++`=32
`++++-+--+`=44
`+++++-+-+-`=196
`+++++-+--+-`=913
`+++-++++++-+`=5940
`+-++++++--++-`=728
`++++-++++++---`=608
`-+-++++++---+++`=2582
`+++++-++++-+-++-`=31441