An Odd Rewriting System
An Odd Rewriting System is an esoteric programming language designed by User:ais523 in 2018. ais523 had noticed that several simple esoteric programming languages seemed to share a similar limitation, and decided to create a language that highlighted the limitation in question, in an attempt to gain more understanding of the issue.
Semantics
A program in An Odd Rewriting System consists an alphabet of symbols, each of which belongs to one of two categories (an odd symbol or an even symbol), except for a special halt symbol that appears in neither category; two definitions for each symbol (an odd definition and an even definition); and an initial string. Both the initial string, and each definition, is simply a (possibly empty) string of symbols from the alphabet.
At the start of execution of the program, a data string (which forms the program's memory) is initialised with the contents of the initial string. Thereafter, execution of the program proceeds as follows: a new data string (replacing the old data string) is formed via concatenating the definitions of the symbols in the old data string. At positions which have an odd number of odd symbols to their left (in the old data string), the odd definition is used; if the position has an even number of odd symbols to its left, the even definition is used.
If at any point there is exactly one halt symbol in the data string, the program halts. If two or more halt symbols appear in the data string, or if the data string becomes entirely empty, this is undefined behaviour.
Syntax
Because the alphabet can be deduced by seeing which symbols have definitions, the syntax of An Odd Rewriting System simply specifies an initial string, followed by a newline, followed by a list of definitions. The source code is in Unicode (and should be represented in a file via using UTF-8); most symbols are represented as Unicode characters with the "cased letter" property (odd symbols have the "uppercase letter" property, even symbols the "lowercase letter" property), with the halt symbol being represented as $.
A definition is written as 0x:string (for an even definition) or 1x:string (for an odd definition), where x is the symbol being defined and string is its definition. Definitions are separated by whitespace.
A program can also contain comments, running from # to the end of the line.
Example
Here's a program for which the data string contains an odd number of odd symbols on cycles 21, 22, 23, etc. (treating the first cycle as being numbered 2; it would be easy enough to add in one or two dummy cycles beforehand if necessary):
Cwg 0c:c 1c:C 0C:C 1C:c 0g:wg 1g:wg 0w:w 1w:C
and here's how the data string evolves as it runs:
Cwg CCwg Ccwwg CCCCwg CcCcwwg CCccwwwg Ccccwwwwg CCCCCCCCwg CcCcCcCcwwg CCccCCccwwwg CcccCcccwwwwg CCCCccccwwwwwg CcCcccccwwwwwwg CCccccccwwwwwwwg Ccccccccwwwwwwwwg CCCCCCCCCCCCCCCCwg CcCcCcCcCcCcCcCcwwg (etc.)
Computational class
An Odd Rewriting System is Turing complete, as 01-2C can be compiled into it.
The following program demonstrates the basic idea:
# Starting state is a small element seed. Cwgḃtḋẋ # Running-XOR counter. 0c:c 1c:C 0C:C 1C:c # Expand the counter, so that it triggers at powers of 2. 0g:wg 1g:wg 0w:w 1w:C # Tape expansion. Produces the seed `botds` from which new elements # grow (an element seed is `bo…tds…`, but it needs to grow twice as # fast as most things, so we start both sides of it at width 2 rather # than 1 so that the width ends up even). Only reacts to signals on # every second cycle. 0x:ẋ 1x:ẋ 0ẋ:x 1ẋ:botdsx # Seed expansion. A seed `b` grows over time until it's reset into a # proper element wrapper. (`d` is similar but reflected.) Only reacts # to signals on every second cycle. 0b:ḃ 1b:ḃ 0ḃ:boo 1ḃ:Ṗ 0o:ȯ 1o:ȯ 0ȯ:o 1ȯ:Ṗ 0d:ḋ 1d:ḋ 0ḋ:dss 1ḋ:Ṙ 0s:ṡ 1s:ṡ 0ṡ:s 1ṡ:Ṙ # The element seed `t` becomes `e` when signalled. 0t:t 1t:e # Log-decaying padding `p`, and its reflected version `r`. Again, # only reacts to signals on every second cycle. 0ṕ:Ṗ 1ṕ:Ṗ 0Ṗ:p 1Ṗ:ṕ 0p:ṗ 1p:Ṗ 0ṗ:p 1ṗ:p 0ŕ:Ṙ 1ŕ:Ṙ 0Ṙ:ŕ 1Ṙ:r 0r:ṙ 1r:Ṙ 0ṙ:r 1ṙ:r # An element `e` becomes `f` for one cycle when triggered, then # deactivates (`ē`). It reactivates at the next trigger. 0e:e 1e:f 0f:ē 1f:e 0ē:ē 1ē:e
Here's how that program evolves over time:
Cwgḃtḋẋ CCwgṖeṘbotdsx Ccwwgpfrḃȯtḋṡẋ CCCCwgṖeṘṖṖeṘṘbotdsx CcCcwwgpfrpṕeŕrḃȯtḋṡẋ CCccwwwgṗēṙṗṖeṘṙboootdsssx Ccccwwwwgpērppfrrḃȯȯȯtḋṡṡṡẋ CCCCCCCCwgṖeṘṖṖeṘṘṖṖṖṖeṘṘṘṘbotdsx CcCcCcCcwwgpfrpṕeŕrpṕpṕeŕrŕrḃȯtḋṡẋ CCccCCccwwwgṗēṙṗṖeṘṙṗṖṗṖeṘṙṘṙboootdsssx CcccCcccwwwwgpērppfrrpppṕeŕrrrḃȯȯȯtḋṡṡṡẋ CCCCccccwwwwwgṗēṙṗṗēṙṙṗṗṗṖeṘṙṙṙboooootdsssssx CcCcccccwwwwwwgpērppērrppppfrrrrḃȯȯȯȯȯtḋṡṡṡṡṡẋ CCccccccwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙboooooootdsssssssx Ccccccccwwwwwwwwgpērppērrppppērrrrḃȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡẋ CCCCCCCCCCCCCCCCwgṖeṘṖṖeṘṘṖṖṖṖeṘṘṘṘṖṖṖṖṖṖṖṖeṘṘṘṘṘṘṘṘbotdsx CcCcCcCcCcCcCcCcwwgpfrpṕeŕrpṕpṕeŕrŕrpṕpṕpṕpṕeŕrŕrŕrŕrḃȯtḋṡẋ CCccCCccCCccCCccwwwgṗēṙṗṖeṘṙṗṖṗṖeṘṙṘṙṗṖṗṖṗṖṗṖeṘṙṘṙṘṙṘṙboootdsssx CcccCcccCcccCcccwwwwgpērppfrrpppṕeŕrrrpppṕpppṕeŕrrrŕrrrḃȯȯȯtḋṡṡṡẋ CCCCccccCCCCccccwwwwwgṗēṙṗṗēṙṙṗṗṗṖeṘṙṙṙṗṗṗṖṗṗṗṖeṘṙṙṙṘṙṙṙboooootdsssssx CcCcccccCcCcccccwwwwwwgpērppērrppppfrrrrpppppppṕeŕrrrrrrrḃȯȯȯȯȯtḋṡṡṡṡṡẋ CCccccccCCccccccwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṖeṘṙṙṙṙṙṙṙboooooootdsssssssx CcccccccCcccccccwwwwwwwwgpērppērrppppērrrrppppppppfrrrrrrrrḃȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡẋ CCCCCCCCccccccccwwwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṗēṙṙṙṙṙṙṙṙboooooooootdsssssssssx CcCcCcCcccccccccwwwwwwwwwwgpērppērrppppērrrrppppppppērrrrrrrrḃȯȯȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡṡṡẋ CCccCCccccccccccwwwwwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṗēṙṙṙṙṙṙṙṙboooooooooootdsssssssssssx CcccCcccccccccccwwwwwwwwwwwwgpērppērrppppērrrrppppppppērrrrrrrrḃȯȯȯȯȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡṡṡṡṡẋ CCCCccccccccccccwwwwwwwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṗēṙṙṙṙṙṙṙṙboooooooooooootdsssssssssssssx CcCcccccccccccccwwwwwwwwwwwwwwgpērppērrppppērrrrppppppppērrrrrrrrḃȯȯȯȯȯȯȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡṡṡṡṡṡṡẋ CCccccccccccccccwwwwwwwwwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṗēṙṙṙṙṙṙṙṙboooooooooooooootdsssssssssssssssx Ccccccccccccccccwwwwwwwwwwwwwwwwgpērppērrppppērrrrppppppppērrrrrrrrḃȯȯȯȯȯȯȯȯȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡṡṡṡṡṡṡṡṡẋ CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCwgṖeṘṖṖeṘṘṖṖṖṖeṘṘṘṘṖṖṖṖṖṖṖṖeṘṘṘṘṘṘṘṘṖṖṖṖṖṖṖṖṖṖṖṖṖṖṖṖeṘṘṘṘṘṘṘṘṘṘṘṘṘṘṘṘbotdsx CcCcCcCcCcCcCcCcCcCcCcCcCcCcCcCcwwgpfrpṕeŕrpṕpṕeŕrŕrpṕpṕpṕpṕeŕrŕrŕrŕrpṕpṕpṕpṕpṕpṕpṕpṕeŕrŕrŕrŕrŕrŕrŕrŕrḃȯtḋṡẋ CCccCCccCCccCCccCCccCCccCCccCCccwwwgṗēṙṗṖeṘṙṗṖṗṖeṘṙṘṙṗṖṗṖṗṖṗṖeṘṙṘṙṘṙṘṙṗṖṗṖṗṖṗṖṗṖṗṖṗṖṗṖeṘṙṘṙṘṙṘṙṘṙṘṙṘṙṘṙboootdsssx CcccCcccCcccCcccCcccCcccCcccCcccwwwwgpērppfrrpppṕeŕrrrpppṕpppṕeŕrrrŕrrrpppṕpppṕpppṕpppṕeŕrrrŕrrrŕrrrŕrrrḃȯȯȯtḋṡṡṡẋ CCCCccccCCCCccccCCCCccccCCCCccccwwwwwgṗēṙṗṗēṙṙṗṗṗṖeṘṙṙṙṗṗṗṖṗṗṗṖeṘṙṙṙṘṙṙṙṗṗṗṖṗṗṗṖṗṗṗṖṗṗṗṖeṘṙṙṙṘṙṙṙṘṙṙṙṘṙṙṙboooootdsssssx CcCcccccCcCcccccCcCcccccCcCcccccwwwwwwgpērppērrppppfrrrrpppppppṕeŕrrrrrrrpppppppṕpppppppṕeŕrrrrrrrŕrrrrrrrḃȯȯȯȯȯtḋṡṡṡṡṡẋ CCccccccCCccccccCCccccccCCccccccwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṖeṘṙṙṙṙṙṙṙṗṗṗṗṗṗṗṖṗṗṗṗṗṗṗṖeṘṙṙṙṙṙṙṙṘṙṙṙṙṙṙṙboooooootdsssssssx CcccccccCcccccccCcccccccCcccccccwwwwwwwwgpērppērrppppērrrrppppppppfrrrrrrrrpppppppppppppppṕeŕrrrrrrrrrrrrrrrḃȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡẋ CCCCCCCCccccccccCCCCCCCCccccccccwwwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṗēṙṙṙṙṙṙṙṙṗṗṗṗṗṗṗṗṗṗṗṗṗṗṗṖeṘṙṙṙṙṙṙṙṙṙṙṙṙṙṙṙboooooooootdsssssssssx CcCcCcCcccccccccCcCcCcCcccccccccwwwwwwwwwwgpērppērrppppērrrrppppppppērrrrrrrrppppppppppppppppfrrrrrrrrrrrrrrrrḃȯȯȯȯȯȯȯȯȯtḋṡṡṡṡṡṡṡṡṡẋ CCccCCccccccccccCCccCCccccccccccwwwwwwwwwwwgṗēṙṗṗēṙṙṗṗṗṗēṙṙṙṙṗṗṗṗṗṗṗṗēṙṙṙṙṙṙṙṙṗṗṗṗṗṗṗṗṗṗṗṗṗṗṗṗēṙṙṙṙṙṙṙṙṙṙṙṙṙṙṙṙboooooooooootdsssssssssssx
The program can be seen to create an ever-growing string of e characters (each of which maintains its identity, although it sometimes becomes ē or f for a while). Each time a new e character is added, each of the e characters becomes an f, in sequence, two cycles apart.
Now, imagine that this program were modified to only update on every second cycle (via giving each character an "alternative version" that doesn't update, analogous to x and ẋ in the program above); that means that oddness on the "off cycles" would not affect the behaviour of the program. Then imagine modifying it again so that instead of a single e/f/ē state machine with three states, there would be two of them (corresponding to 0 and 1 from the 01-2C program), with a much larger number of states (specifically, the state machine would remember whether it had observed oddness on the previous 2s off cycles, where s is the maximum length of a search string in the 01-2C program, in addition to maintaining the previous behaviour of the state machine). Next, we adapt the 1 state machine to use an odd symbol on the off cycle immediately after it becomes f (and at no other time; the 0 state machine stays even constantly). Finally, we can then implement the non-degenerate rules from the 01-2C program via causing the 0 state machine to transition to a state from the 1 state machine (or vice versa) at times that the symbol within the 01-2C program would be replaced (the only information it needs to determine this is what symbols exist to its left in the 01-2C state string, which it knows due to the state containing a memory of the oddness previous 2s off cycles; there's a 1 x spaces to the left if oddness was observed 2x off cycles ago, and a 0 otherwise).
One unfortunate problem with this computational class proof is that it incurs an exponential slowdown. ais523 conjectures that any Turing-complete construction for An Odd Rewriting System will have this problem (although would be interested to be proved wrong on this).
Implementations
- Interpreter in Perl
- An Odd Rewriting System/Odd.hs, a partial implementation in Haskell
- An Odd Rewriting System/odd.rs, an implementation in Rust