T-rexes

T-rexes

Paradigm(s)	grammar
Designed by	Xia Li-yao
Appeared in	2024
Memory system	tape
Dimensions	one-dimensional
Computational class	Turing complete
Reference implementation	https://blog.poisson.chat/posts/2024-06-18-turing-regex.html
Influenced by	regular expressions

T-rexes (Turing regexes) is a Turing complete extension of regular expressions.

T-rexes operate on an infinite bidirectional tape of symbols, and their operation is able to modify the tape. The head is referred to as a T-rex, with the program (grammar) being the tale.

The syntax is similar to regular expressions, consisting of 3 structures which always match and modify the state, and 4 structures which conditionally match.

State modifying:

• $s!$ writes the symbol $s$
• $>$ shifts the T-rex right
• $<$ shifts the T-rex left

Conditional:

• $s?$ checks for the symbol $s$, resulting in a success if found, otherwise failure
• $e_{0}e_{1}$ evaluates the expression $e_{0}$ followed by $e_{1}$ if both are successful, otherwise neither
• $e_{0}|e_{1}$ evaluates either the expression $e_{0}$ or $e_{1}$ but not both
• $e*$ evaluates the expression $e$ zero or more times

Officially, the language only supports the set of digits $\lbrace 0,1,2,3,4,5,6,7,8,9\rbrace$ for the tape symbols.

Notably, using solely the conditional operations with $>$, T-rexes is equivalent in power to regular expressions. With the ability to mogrify state with $s!$ and retrieve prior state with $<$ the language is Turing complete.

Regular expression example:

b(a|i)t

This matches either bat or bit, and is equivalent to this tale:

b?>((a?|i?)>)t?>

When run against the input tapes bat or bit the machine will find a successful match. If run against a tape like bot then it cannot find a successful match for the tape, just like for the regular expression.

The language is nondeterministic, for instance, 0!|1! may write 0 or 1, both are valid executions. Similarly, (1!>)* may write any number of 1s onto the tape. Deterministic programs can be written, however, by restricting alternation and repetition to guarded forms $(s_{0}?e_{0}|s_{1}?e_{1})$ and $(s_{0}?e)s_{1}?*$. This does not lose generality.

Xia demonstrates a method to compile brainfuck into an extended form of T-rexes. The method adds an antimatch $s\sim$ which is the complement of $s?$, as well as $+$ and $-$ which increment and decrement symbols on the tape modulo 256. This extension is Turing complete without alternation $e_{0}|e_{1}$. A simpler deterministic reduction from Smallfuck is possible without the use of antimatch, but requires alternation:

Smallfuck	T-rexes
>	>
<	<
*	(0?1!|1?0!)
[ ... ]	(1? ... )0?

Observe that if we remove alternation, we effectively are afforded move left <, move right >, assign true 1!, assign false 0!, while true (1? ... )0?, and while false (0? ... )1?.

User:Otesunki provided an alternate translation from Smallfuck to this double while loop language, proving that T-rexes is complete without alternation:

Smallfuck	Dual while	T-rexes
>	>>	>>
<	<<	<<
*	>0<{>1<0}>[<1>0]	>0!<(0?>1!<0!)1?>(1?<1!>0!)0?
[ ... ]	{ ... }	(0? ... )1?