What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?

Question

In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond matching primes and powers of 2 (both of which were puzzles in the Regex Golf site). This is a dialect of regex that includes negative and atomic positive lookahead, and backreferences that are erased when the loop they were defined in starts a new iteration. (They're of course not "regular expressions" in the CS sense).

A unary regex function takes a string of identical characters as input (x is used for clarity instead of 1), whose length represents $n \in \mathbb{N_0}$. Its output may be either a non-match (which can represent "false"), or any $m \le n$ (which can represent "true", ignoring $m$'s value).

Due to the limitations on ECMAScript backrefs, only one variable* can be changed from iteration to iteration in a loop – the the $tail$ following the current cursor position, in such a way that it is decreased by at least $1$ on every iteration (by moving the cursor forward). All other variables (backrefs) can only capture a value once (per iteration if in a loop) which cannot be greater than the value of $tail$ at the time of its definition. An additional constraint is that when searching for a number that satisfies some condition, the current value being tested must be subtracted from $tail$ before its properties can be tested (this can be avoided by defining a new operation, non-atomic lookahead, which allows the regex engine to backtrack into the lookahead from outside it). And $n$ can only be operated on directly when the cursor is at the leftmost position, i.e. $tail=n$.

Because of this, the approaches available in more powerful regex flavors (e.g. Perl, PCRE, Java, .NET, Python, Ruby) won't work, for example ^(^x|xx\1)*$ can't be used to match squares.

I was suprised and fascinated to find that the power of unary ECMAScript regex goes rather deep indeed:

• Match primes - ^(?!(xx+)\1+$)xx
• Match powers of 2 - ^(?!(x(xx)+|)\1*$) or ^(?!(x*)(\1\1)+$) or ^((x+)(?=\2$))*x$
• Match powers of 10 - ^((x+)\2{8}(?=\2$))*x$
• Match prime powers - ^(?!(((x+)x+)(?=\2+$)\2*\3)\1+$)x
• Match Nth powers - ^((?=(xx+?)\2+$)((?=\2+$)(?=(x+)(\4+$))\5){N})*x?$
• Match correct statements of multiplication - ^x(x*)·?(x*)·?x\1=(?=(x(\1\2))\1(\3*)\4*$)\3*$\5 (takes its input as A·B=C; doesn't handle zero); this uses the Chinese remainder theorem. Although it's not purely unary (with delimiters · and =), its multiplication logic can be used within a purely unary regex.
  • Fully generalized, with handling of zero: ^(?=(x?(x*))·(x?(x*))).*=(?=.*((?=\1*$)(?=\3*$)(?=\1\4+$)\3\2+$|$\1|$\3))\5$
• Division and remainder - (x(x*)),(x*?)(?=\1*$)(x?(x*))(?=\4*$)((?=\2+$)\2\5*$|$\4)
  • This turned out to be quite interesting. The algorithm can't be proved using the Chinese remainder theorem, but finally does have a proof (linked above) thanks to H.PWiz. There are shorter variants that can be used when certain inequalities regarding the dividend and divisor are guaranteed to be met.
• Match squares - ^(x(x*)|)(?=(\1*)\2+$)\1*$\3 (shorter than the above Nth powers regex thanks to generalized multiplication)
• Match perfect powers ($a^b$ where $b>1$) - ^(x+)((\1(x+))(?=(\3*)\1*$)\3*(?=\4$\5))+x$|^x?$
• Match triangular numbers - ^((((x*)x?)\3)x)?(?=\4(\1*)\2*$)\1*$\5
• Match Fibonacci numbers - ^(?=(x*).*(?=x{4}(x{5}(\1{5}))(?=\2*$)\3+$)(|x{4})(?=xx(x*)\5)\4(x(x*))(?=(\6*)\7+$)(?=\6*$\8)\6*(?=x\1\7+$)(x*)(\9x?)|)(\9\10(\5\10)\12?|xx?x?|x{5}|x{8}|x{21})$
• Match factorial numbers - ^(((x+)\3+)(?=\3\3\2$)(x(?=\3+(x*))(?=\5+$)(?=((x+)(?=\5\7*$)x)\6*$)\3+(?=\5\7$))*\3xx|x?)x$
• Match abundant numbers - ^(?=((?=(xx+?)\2+$)(x+)\3*(?=\3$))+(?!\2+$)(?=(xx(x*?))\4*$)x((x(x*))(?=\7*$)\5\8+$))(?=(x(x*))(?=\9*$)\6\10+$)(?=(x*?)(?=(x(\6\7))+$)(x(x*))(?=\14*$)(?=\13+$)\15+(?=\11\11|(x))\13$)((?=(x*?(?=\9*$)(?=(x+)(?=\10+$)\19*$)(^\14{2}\16|)))(?=(xx+).*(?=\9$)(?=\21*(?!\19)\21$)(|(x+)\23*(?=\23$))(?!(xx+)(?!\21+$)\24+$)(?=(x*)(?=xx(x\25)*$)\21\25*$)(\21+$))(?=.*?(?!x\18)(?=(x(\27\25))+$)(x(x*))(?=\30*$)(?=\29+$)\29\31+$|)(?=\30(x*)(?=\9*$)(\21\10+$))\32)+\33$ (there is a shorter version, but I haven't proved it to be correct to infinity yet)
• Return $\lfloor{\log_2 n}\rfloor$ - (?!(x*)(\1\1)+$)(?=(x+)\3)(?=((?=(x+)(?=\3)\5(((x*)(?=\8$)x)+$))\6)*)\5x|\b$
• Return $\varphi(n)$ - (?=((xx+)(?=\2+$)|x+)+)(?=((x*?)(?=\1*$)(?=(\4xx+?)(\5*(?!(xx+)\7+$)\5)?$)(?=((x*)(?=\5\9*$)x)(\8*)$)x*(?=(?=\5$)\1|\5\10)x)+)\10|x
• Return $\lfloor{n\sqrt{1/2}}\rfloor$ - (?=(x(x*)).*(?=\1*$)\2+$)(?=(x\1)+(x?(x*)))(?=\4(x(x*?))\1+$)(?=.*(?=(?=\4*$)\4\5+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\9))(?=.*(?=(?=\4*$)(?=\6*$)(?=\4\7+$)\6\5+$|$\4)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\13))(?=.*(?=\12\12\9$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\17))(?*.*?(?=((?=\3*(x?(x*)))\21(x(x*?))\1+$)))(?=.*(?=\23*$)(\23\24+$))(?=.*(?=(?=\21*$)\21\22+$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\27))(?=.*(?=(?=\21*$)(?=\23*$)(?=\21\24+$)\23\22+$|$\21)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\31))(?=.*(?=\30\30\27$)(x*?)(?=\3*$)(x?(x*?))(\1+$|$\35))(?=.*(?=\26\26)(?=\3*(x*))(\1(x)|))(?=.*(?=\34\34\40)(?=\3*(x*))(\1(x)|))(?=(?=(.*)\13\13\17(?=\6*$)\6\7+$)\44(x+|(?=.*(?!\16)\41|(?!.*(?!\38)\8).*(?=\16$)\41$))(\25\31\31\35){2}\43$)\20|xx?\B| - uses (?*...); without that, it'd be about twice as long or more. This can clearly be extended to any algebraic number $0<x<1$; $x=\sqrt{1/2}$ is probably the simplest irrational example.

*So in order to emulate more than one mutable variable in a loop, a tuple must be encoded into a single number. For example:

• The encoding $(a,b,j)\to a+b^2+jC$, where $j$ is a decreasing iteration count, works as long as $a\le 2b$ and $(b+1)^2\le C$ always remain true and $(j_0+1)C-1\le n$. The values of $a$ and $b$ may increase or decrease from iteration to iteration.
• With the encoding $(a,b,j)\to a+bC+jC^2$, where $a<C$ and $b<C$, the values of $a$ and $b$ may increase or decrease from iteration to iteration without any inequality being enforced between them.
• The encoding $(a,b)\to n-a-b^2$ works as long as $a\le 2b$ and $a+b^2\le{n\over 2}$ remain true and $a$ and/or $b$ increase on every iteration.

I have written a regex engine to facilitate exploring mathematical regexes. It's much faster than traditional regex engines when operating on unary numbers, not only because it can represent them as integers rather than strings, but also thanks to optimizing for common operations done on unary numbers. I also implemented non-atomic lookahead / molecular lookahead (?*...), which was later also adopted by the regex engine PCRE2.

In 2019 I began to post mathematical ECMAScript regexes on CGCC, which got Grimmy and H.PWiz interested in the subject. Some nice advancements came from this, including huge golf optimizations, and at least one additional function being implemented that I previously wasn't sure was possible, $\varphi(n)$, and a rigorous proof of the division algorithm. But my core questions remain unanswered.

Please note that although there are five questions below, I will upvote and accept any good answer to even just one of them.

My questions are:

1. Can any transcendental number $0<x<1$ be "computed" by an ECMAScript regex in the same way as $\sqrt{1/2}$ is computed by the regex above, i.e. by returning $f(n)=\lfloor{nx}\rfloor$? Trivial examples like $1.101001000100001...^{-1}$ might be possible. What about $\pi^{-1}$ or $e^{-1}$, or numbers whose class is not known, such as $\gamma$ or $\delta$?
2. How precisely can the power of unary ECMAScript regex be characterized? Can any primitive recursive functions in $\mathbb{N_0}$ where $f(n)\le n$ be proven to be impossible? It's obviously somewhere below primitive recursive in power, as its limitations surely make implementing some primitive recursive functions impossible. For example, I'm pretty sure $\pi(n)$ is impossible. (Given infinite scratch space to work in, instead of just $n$, it would be exactly primitive recursive in power – just search for an enormous number encoding all the relations to be tested, and consume them one at a time.)
3. Are there any functions that can be implemented with molecular lookahead (?*...) but not without it? Grimmy came up with an interesting problem that comes close: Match $n$ iff there exist perfect powers $a\le n$ and $b\le n$ (using the definition of perfect powers above) such that $n-a = (n-b)^m$ where $m>1$. This gives the sequence $20, 28, 29, 35, 41, 52, 68, 72, 89, 90, 126, 130, 133, 174...$
   • In ECMAScript+(?*) this is just ^(?*(x(x*)x+))(?!(\1|x\2)(?!(x+)((\4(x+))(?=(\6*)\4*$)\6*(?=\7$\8))+x$|x$)).*(?=\1$)\2((\2(x+))(?=(\10*)\2*$)\10*(?=\11$\12))+x$.
   • In ECMAScript it's still possible: ^(?=(x*)\1(x*))((x+(x*))(x?))(?=\6*(x?)).*(?=\1$)(?=.*(?=\2\7)(xx)?((\7?)x*))(?=\9*(x?))(?!\10(\4|\5)\6(?!$\11|(\11(x*))(?:(?=(?=\13$\9|(?=(\13\13\9)+(x*))(?=.*(?=\15)\16(x*))\17\15*$)((x*)(x|(?=(x))))(?=\21((?=\18$)|(?=(\18\18\21))(?=\18\18\23*(x*))(?=.*(?=\23)\24(x*))(?=\25\23*$)))((?=.*(?=\21$)\11(x*)|(x))(?=(\27\28))\21\14\28((?=.*(?=\29$)\20$)\19$|(?=(\19\19\20)+(x*))(?=.*(?=\31)\29\32(x*))\33\31*$)))(?=.*(?=\21$)\11$)\26\14)+$)).*(?=\6\4$)(\6(\5))(?:(?=(?=\34$\7|(?=(\34\34\7)+(x*))(?=.*(?=\36)\37(x*))\38\36*$)((x*)(x|(?=(x))))(?=\42((?=\39$)|(?=(\39\39\42))(?=\39\39\44*(x*))(?=.*(?=\44)\45(x*))(?=\46\44*$)))((?=.*(?=\42$)\6(x*)|(x))(?=(\48\49))\42\35\49((?=.*(?=\50$)\41$)\40$|(?=(\40\40\41)+(x*))(?=.*(?=\52)\50\53(x*))\54\52*$)))(?=.*(?=\42$)\6$)\47\35)+$ - this works by pair-encoding variables.
     With a little modification, it seems it should be possible to design a function that is not possible without (?*). But could it be proven to be impossible?
4. Are there any functions that can be implemented with right-to-left evaluated variable-length lookbehind (?<=...), as in the ECMAScript 2018 standard, but not with (?*...)? In most ways lookbehind gives a superset of molecular lookahead's power. ^(?*A)B can be transformed to ^A(?<=(?=B)^.*). When we're not at the $tail=n$ position, (?*A)B can become (?<=(.*))A(?<=^\1(?=B).*). Lookbehind can directly do things that molecular lookahead cannot; most notably, ^...(?:...(?<=(?=A)^.*)...)*...$ uses it to do tests directly on $n$ from within a loop. Are there functions that require this functionality, and can't be implemented with just (?*...)?
5. Are there functions that can be implemented with (?*...) but not with (?<=...)? Although the latter may seem at first to offer a strict superset of the former's functionality, this may not be the case. (?:(?*A)B)* can only be transformed to (?:(?<=(.*))A(?<=^\1(?=B(.*)).*).*(?=\2$))* if A never advances the cursor by more than B.