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

41–50 of 102 posts

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

#41

Post by FeepingCreature »

noctune wrote: post #32
retrac wrote: post #17

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…

Personally, I use "regex" for the informal string-matching/rewriting engines found in most languages and "regular expression" for the formal definition.

By which, of course, this submission title is a lie.

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

#42

Post by necovek »

FeepingCreature wrote: post #41
noctune wrote: post #32

Earlier quoted context omitted.

Personally, I use "regex" for the informal string-matching/rewriting engines found in most languages and "regular expression" for the formal definition.

By which, of course, this submission title is a lie.

I don't think the GP is the original poster, so them claiming how they "personally" differentiate between the two does not make the submission title a lie.

We don't know how original poster differentiates.

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

#43

Post by underdeserver »

unhammer wrote: post #38
johnfn wrote: post #34

Earlier quoted context omitted.

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

Only every time they claim a major mathematical breakthrough using regular expressions.

Nobody claimed that.

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

#45

Post by lapinot »

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

The important point here was given infinite space.

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

#46

Post by evanb »

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.

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

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

#47

Post by aleph_minus_one »

evanb wrote: post #46
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.

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.

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

#48

Post by mjan22640 »

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…

A finite self referential algorithm that checks all numbers for being prime does exist. Running it on a finite computer will eventually hit the bounds of the computer, but that is a limitation outside of the algorithm.

A finite regular expression that checks all numbers for being prime cannot exist already in principle.

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

#49

Post by tiborsaas »

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.

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

#50

Post by comonoid »

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.

You can certainly do calculations with apples, but doing RSA encryption with them is just impractical.
Post reply on HN