Turing complete regex

Turing-complete Regexes (commonly abbreviated as T-Regex) is an esoteric programming language that extends standard regular expressions with stack operations and recursive execution, making it Turing complete.

Overview

Turing-complete Regexes maintains all the standard regex pattern matching capabilities while adding a stack memory model and control structures that enable arbitrary computation. The language processes input text through pattern matching while maintaining both a matches list and a separate stack for computation.

Language Specification

Core Components

• Matches List: The traditional list of regex matches and capture groups
• Stack: An unlimited LIFO storage for computation
• Input String: The text being processed

Extended Commands

Command	Description
-	Remove the last item from the matches list and push it to the stack
&	Pop the top item from the stack and print it to STDOUT
#expr	Execute expr as a sub-regex in a sandboxed environment using the last stack item as input, then push all matches joined without separators to the stack
"text"	Push the literal string "text" to the stack
(expr)?(if_matched);(else)	Conditional execution
EOF	Implicitly print all matches joined without separators

Execution Model

1. Patterns are matched against the input string as in standard regex 2. The matches list contains all successful matches and capture groups 3. Stack operations manipulate additional memory 4. At end of execution, all remaining matches are printed

Computational Class

Turing-complete Regexes is 'Turing complete because:

• It has unbounded memory via the stack
• It supports conditional branching via the ? operator
• It enables recursion and subroutine calls via the # operator
• The stack can grow arbitrarily during computation
• Complex control flow can be implemented through recursive pattern application

The # operator is particularly crucial as it allows the language to perform computation on its own stored data, similar to recursive function calls in conventional programming languages.

Interpreter

A T-Regex interpreter can found here.

External Resources

• None yet