81–90 of 102 posts
Earlier quoted context omitted.
But that argument is not interesting. "We can't count arbitrarily high because the universe is finite." Yeah, duh. (Observable universe, for the pedants.) It's more interesting to ask: suppose you did have a magical stick of RAM that had infinite storage, and suppose you augmented your computer to store and query that memory. Then -- yes -- your computer could determine whether any number, however large, is prime. An…
If you have an infinite stick of RAM, regular expressions wouldn't be FSMs, either, they could have infinite state space. They would terminate in finite time that is exponential in the size of the prime but nevertheless would still halt.
Earlier quoted context omitted.
Russ Cox has an excellent write up on it. "Regular Expression Matching Can Be Simple And Fast" (2007) https://swtch.com/~rsc/regexp/regexp1.html
Alas that approach only works well for your basic regular expressions that support Kleene-Star, concatenation and union. Regular languages are also closed under intersection and taking prefix etc (see https://en.wikipedia.org/wiki/Regular_language#Closure_prope... ), and if you want to expose those operators in your regular expressions, Russ Cox's technique doesn't really work.
I also suspect that this might result in a combinatorial explosion of fused terms, but that's irrelevant as we're only worried about whether intersection can be implemented in Russ Cox's method, not whether a regular expression might require several earths or so worth of RAM to hold :)
Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`?
Earlier quoted context omitted.
Correct. The \1 holds some external state... but this can be overcome with a different architecture. If you want to start down that rabbit hole. Extending finite automata to efficiently match Perl-compatible regular expressions https://www.researchgate.net/publication/221325349_Extending... > Regular expression matching is a crucial task in several networking applications. Current implementations are based on one of…
> The awkward part is that a PCRE is demonstrably more powerful than a regular language, but not as powerful as a CFG Hmm, there's a reduction of 3-cnf-sat to perl regexps, making them NP-complete. As CFGs are in NP... https://perl.plover.com/NPC/NPC-3SAT.html
https://www.pcre.org/original/doc/html/pcrepattern.html#SEC2...
\( ( [^()]++ | (?R) )* \)
Technically not a regular expression, as (intuitively) the backreference has to “count” the number of 1’s that were matched. Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers). The 2022 discussion has a more formal proof using the pumping lemma.
Fun fact about the pumping lemma - my best friend's grandparent worked on it (Eli Shamir). When we were taught it during my bsc the TA who knew he was the grandson of one of the inventors, asked during the lecture where he was, if he could say something about his grandfather, and it turns out he played hockey from the class to work on something else, embarrassing! The pumping lemma is a great milestone in this field,…
If the "working on something else" means "working on some hard research problem", this is not embarrassing, but stylish. :-)
Took me a while to realise that it is not actually validating whether a given number is a prime number or not. It is validating whether a string of consecutive 1's has a prime length. In other words, it can't tell whether "3" is prime, unless you express it as "111". Much less exciting.
Sorry, but how is this different than pointing to three apples and explaining someone that this is what three is? Would you say it's not three because they are apples? I think it does not really matter how you represent the number. After all, all you see on your screen is "fake" it's just binary under the hood.
And here, validating a string of ones is simply not what anyone would mean if you said "check whether this number is a prime number" without any qualification, so I agree that whilst still cute, the title is a bit click-baity and not at all what I expected it to be about either.
EDIT: it seems though that the original post, shared via archive.org elsewhere in the thread does do this for what one would normally assume -- and does so by using `(1 x shift) !~` -- so if anyone else was confused, read the original post.
Earlier quoted context omitted.
> Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers). The machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. Informally, regular expressions like in…
> The machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. I'm not sure how that's relevant. Even given infinite space, there still wouldn't exist a Regular Expression (the CS kind) you could write down in finite time that would match only primes. At least IIRC, it's been a 20+ years since I last took a Discrete Math course…
Your memory is correct and there is very simple intuition for this. Regular languages are those that can be matched by a machine with bounded memory. So, let's say that bound is "n" bits. Then your machine will not be able to read in unary strings larger than 2^n.
Earlier quoted context omitted.
Only every time they claim a major mathematical breakthrough using regular expressions.
Nobody claimed that.