14
$\begingroup$

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:

*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.

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...$
  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.
$\endgroup$
2
  • $\begingroup$ "Can any transcendental number computed": No, because transcendental numbers are uncountable whereas program code strings are countable. $\endgroup$
    – Nayuki
    Aug 5, 2021 at 18:35
  • $\begingroup$ @Nayuki That logic doesn't work. The equivalent of only a finite number of digits of the transcendental number need to be calculated. By your logic, it wouldn't even be possible in a Turing-complete language to take a natural number N as input and calculate the first N digits of pi as output, but that is possible. (You may be falsely equating transcendental numbers with uncomputable numbers.) $\endgroup$
    – Deadcode
    Aug 12, 2021 at 8:37

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.