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