We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for matching the ith captured subexpression). It is known that such regexes have far more expressive power than the regular expressions defined in formal language theory.
I am interested in the following two categories of arithmetic functions on the unary representation of the natural numbers (i.e., a sequence of $n$ symbols a represents the number $n$):
Transducers
In the first category, a function is given by a search string, a replace string and an operation Replace All, which substitutes the replace string to any occurrence of the search string. For instance:
- $\lambda n. 2n$
"a""aa"
- $\lambda n. \frac{n}{2}$
"(a*)\1a?""\1"
- $\lambda n. \frac{n}{3}$
"(a*)\1\1a?a?""\1"
- $\lambda n. n \bmod 2$
"(a*)\1(a?)""\2"
- Collatz function
"(a*)\1$|((a)*)""\1\2\2\2\3"
- Smallest divisor greater than 1
"(aa+?)\1+$|(a*)""\1\2"
Acceptors
In the second category, a predicate is given by a regex pattern and an operation Match which tries to match the pattern from the beginning of the input sequence. The output is interpreted as True is the match succeeds, and False otherwise. For instance:
is_even"(aa)*$"
is_odd"a(aa)*$"
is_not_prime(from Neil Kandalgaonkar)"a?$|(aa+)\1+$"
Question
Is it possible to devise a transducer for $\lambda n. n^2$ or an acceptor for is_prime? More generally, which arithmetic functions and predicates can be defined in such a model?
