Myth
Myth is a minimalist Turing-complete non-deterministic esoteric programming language based on the string-rewriting paradigm. Its reference implementation was created by User:Plugnburn for 140byt.es contest in JavaScript (ECMAScript 5 standard) on July 30, 2013 and is only 137 bytes long.
Language structure
The interpreter is non-interactive. It takes the Myth code in JSON format as the input and returns the final state as the output.
Myth code consists of key-value string replacement rules.
The string "_" (single underscore) is used as the key to specify the initial state, so it's the only string in Myth that cannot be used as a rewriting rule.
Myth computational model is similar to those in Thue, PROLAN/M and REBEL. The interpreter takes the initial state, repeatedly loops through the rules and applies the first matching substitution, then repeats the outer loop until no rules match the current state, and returns the final state to the environment.
Examples
Hello world:
{"_":"Hello world!"}
Or more complicated version that also shows the rewriting concept:
{"a":"Hello","b":"world","_":"a b!"}
Binary number increment (a port from Thue page):
{"1_":"1++","0_":"1","01++":"10","11++":"1++0","_0":"_","_1++":"10","_":"_11111111111_"}
Implementation
Reference implementation in JavaScript (137 bytes):
function(m,y,t,h){m=JSON.parse(m);for(y=m._;h=1;){for(t in m)if(t!="_"&&~y.indexOf(t)){y=y.replace(t,m[t]);h=0;break}if(h)break}return y}
Shorter implementation (106 bytes):
(m,y,t,h)=>{h=m=JSON.parse(m);for(y=m._;h;)for(t in h=0,m)if(!h&&t!="_")y=y.replace(t,x=>m[h=t]);return y}
Turing completeness
As the Myth code can be transparently translated to Thue and vice versa (moreover, Myth code can be considered a JSON-serialized version of Thue code), Myth is also Turing-complete.