NRSRSSOMN

NRSRSSOMN (Nameless Random String-Rewriting Systems Scribbled On Math Notebook) are a collection of string-rewriting systems created by User:EzoLang. They are presented here in a loose time/feature order.

NRSRSSOMN-0 (< and >)

In the most basic form, there are only 2 commands: < and >. < copies into the new string the symbol to its left, except if it is in the leftmost position of string, in which case it does nothing. > works the same as <, but copies from right instead. From this it is pretty trivial to see that that all NRSRSSOMN-0 programs will terminate, and the maximum amount of memory used will never exceed that of the seed string. This level can be easily simulated by the one-dimensional CA W184, in fact, they are essentially the same.

NRSRSSOMN-1 (<, > and x)

Same as NRSRSSOMN-0 but also adds one additional command, x. When run, it will append the symbols from both its sides to the next string. NRSRSSOMN-1 programs that run infinitely are easy to construct, for example xx, xx< and >xx<. Also, most non-halting patters in NRSRSSOMN expand, thus it cannot be simulated with a Bounded-storage machine and if author is not wrong, shows that NRSRSSOMN is at least in the level of PDA computationally.

NRSRSSOMN-2 (<, >, x and |)

Again, old commands stay the same. | makes symbols operating on it act like the entire rest of line - including the | itself - is one symbol to be copied. For example, >|> would copy |> to the output. Author is pretty sure NRSRSSOMN-2 has higher computational class than NRSRSSOMN-1, but cannot prove it. At least there are more interesting patters in it.

NRSRSSOMN-3 (<, >, x, | and ())

Brackets act kinda like | but they are effective to only one direction, from "outside" to "inside". On the other direction, the brackets are just skipped over like they didn't exist. Also, the effect of brackets doesn't necessarily last until the end of line, but can be terminated by single bracket that "closes" the brackets. Brackets don't need to be balanced, thus the > in >(a(b)c) only copies (a(b).

NRSRSSOMN-4 (<, >, x, |, () and [])

Square brackets function the same as normal ones, except that they need to be balanced. Thus > in >[a[b]c] will copy [a[b]c], while in >(a(b)c) the c) part would be left off. With these, x can be implemented as [<>], making it redundant but kinda nice syntactic sugar.