Your Time Is Up

Your Time Is Up is a string-rewriting esolang by User:PythonshellDebugwindow.

Syntax and Semantics

Programs in Your Time Is Up are in binary, composed entirely of 1s and 0s. They all match the regular expression ((?:(1+0)(1+0)([10]{N})([10]{M}))*)0([01]*). Let's go through this in more detail (the meanings of N and M will be explained).

((?:(1+0)(1+0)([10]{N})([10]{M}))*)

This is the main part of the program, where the rewriting rules are.

(1+0)

A series of 1s followed by a 0. The amount of 1s is important; let's call the amount N.

(1+0)

Another series of 1s followed by a 0. The amount of 1s is still important; let's call the amount M.

([10]{N})

A binary sequence of length N (see above). Specifies a part of the binary string to replace (a p‑string).

([10]{M})

Another binary sequence, this time of length M (see above). Specifies the replacement (an r‑string) for the part of the binary string specified previously (see directly above).

(?:''...''')*

Zero or more rewriting rules can be written in a program. 0([01]*) If the first character in what would otherwise be (1+0) is 0, the rewriting section is ended immediately and the rest of the program is interpreted as the initial binary datastring.

Execution consists of picking, from the list of rules, a random rule whose p‑string exists as a substring somewhere in the datastring, and replacing that substring by the rule's r‑string. This goes on until no rules can be applied, at which point the program ends.

Computational class

Translation to a version of Thue with no IO can be achieved easily enough. Simply encode the datastring in binary using ASCII. The ::= rule can be replaced with 0. Since all Thue rules are finite in length, and therefore can be encoded in a finite amount of 1s, Your Time Is Up is Turing-complete.