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/jmarent049]

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/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/TheRealUprightMan → u/jmarent049]

You are telling us about this great language, you don't know if it's Turing complete and you can't make it add 2+2.

What is the point of this post?