Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A regular expression to check for prime numbers (2007)

noulakaz.net

Post reply on HN
Print view View original

51–60 of 102 posts

Re: A regular expression to check for prime numbers (2007)

#51

Post by tannhaeuser »

wongarsu wrote: post #11
CoastalCoder wrote: post #10

Earlier quoted context omitted.

Agreed. I read the post because the result was so shocking. TIL that the computer-sciencey definition of RE isn't the only one in use.

When programmers say regular expression they usually mean Perl Compatible Regular Expressions (PCRE). Or I guess PCRE-compatible expressions, since there are other implementations of the same syntax out there. If you go back far enough in time they were once regular expressions in the computer science sense, but then features got added, and now they are incredibly powerful but can take basically infinite memory and t…

[flagged]

Re: A regular expression to check for prime numbers (2007)

#52

Post by kaba0 »

retrac wrote: post #17
tylerhou wrote: post #7

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.

> 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

Come on, can we drop this useless trivia that floats around? No, computers are Turing-machines for all practical purposes and no the memory is not the tape, unless your computer is sandboxed from everything. As soon as it has some side effect channels, its “tape” can be as large as needed. For example, it can use the internet to store petabytes of state. But if we want to be more pedantic, it can control and observe physical things, making the whole universe its state space.

Which is still finite, so yeah, even more pedantically you are right due to mathematical infinity not existing, but the actual distinction of a Turing machine is “lazy”, if you don’t hit the limit, you may as well reason as if it were a Turing machine.

Re: A regular expression to check for prime numbers (2007)

#53

Post by kaba0 »

dheera wrote: post #26
Quekid5 wrote: post #24

Earlier quoted context omitted.

> 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…

> 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. The point is, neither would there exist a non-(Regular Expression) method that could do such, if you're running it on a finite state machine (your computer).

There is, the property of being a Turing machine would only be thrown out when you actually hit the limit. Besides computers being able to modify state not only in their memory but e.g. outside memory, I can also look at my computer as a lazy-taped Turing machine that chugs along writing only to its memory, and when it were to go off it pauses and waits for me to add additional memory.

This is just useless pedantism that diminishes the very imporrant categorization of Chomsky.

Re: A regular expression to check for prime numbers (2007)

#54

Post by kaba0 »

dheera wrote: post #30
tylerhou wrote: post #28

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.

A finite state machine can’t have infinite state space.. also, you can write a finite Turing program that does exactly that, but you can’t write a finite description of an “infinite” state space, which is the whole point.

Ad absurdum everything would be computable (recognizable) by FSMs, simply by listing all the infinite number of possibilities. listOfAllPrimes.concat(“|”), here you are..

Re: A regular expression to check for prime numbers (2007)

#55

Post by cubefox »

tylerhou wrote: post #7

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.

Technically, a computer is also just a large finite state machine. Which suggests computability theory is unable to accurately account for the intuitive difference between computers and simpler automatons. I suspect it has something to to with the computational time/space complexity of the algorithms they are able to execute.

Re: A regular expression to check for prime numbers (2007)

#56

Post by Tade0 »

johnfn wrote: post #34
tylerhou wrote: post #7

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.

Come now, every time a colleague says they parsed a file with a regex in javascript, do you turn to them and tell them "well, you didn't actually use a _regular_ expression..."

I do find it useful to know that regular expressions in JS(and many other languages really) are not actually regular and why - allows one to decide if a given problem can be solved at all using them.

Re: A regular expression to check for prime numbers (2007)

#57

Post by IshKebab »

tiborsaas wrote: post #49
stevage wrote: post #29

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.

It's less interesting because decoding decimal numbers with regex is a much more impressive feat.

Re: A regular expression to check for prime numbers (2007)

#58

Post by Tainnor »

aleph_minus_one wrote: post #47
evanb wrote: post #46

Earlier quoted context omitted.

Could the AKS primality test, which showed that PRIMES is in P, be implemented as an honest regular expression? Presumably not because then we'd know that PRIMES is not just in P but is a regular language, which would be too good to be true. https://en.wikipedia.org/wiki/AKS_primality_test

Via the pumping lemma, you can easily prove that testing whether a number is a prime number cannot be implemented as a regular expression.

Via the context-free pumping lemma, you can even prove that prime numbers don't form a context-free language either.

Re: A regular expression to check for prime numbers (2007)

#59

Post by jimhefferon »

hoytech wrote: post #23

You can also factor integers with Regexp::Exhaustive: https://metacpan.org/pod/Regexp::Exhaustive#Finding-all-divi... And if you're in Toronto in 3 weeks time, come see Abigail (the original inventor of the prime number regexp) solve the N-Queens problem with regexp: https://tprc2023.sched.com/event/1LhoB/the-n-queens-problem-...

Thank you for crediting Abigail.

Re: A regular expression to check for prime numbers (2007)

#60

Post by oneeyedpigeon »

stevage wrote: post #29

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.

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

I don't think you've really explained why those two things are different. They're different methods but they're checking the exact same thing.

Post reply on HN