Re:A regular expression to check for prime numbers
by petters on Wednesday June 21, 2023 @02:21AM
(#36415059)
They said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?
Re:A regular expression to check for prime numbers
by cubefox on Wednesday June 21, 2023 @07:05AM
(#36416960)
I think with "unbounded but finite" he meant potential infinity rather than actual infinity.
Re:A regular expression to check for prime numbers
by finitemonkey on Wednesday June 21, 2023 @05:49PM
(#36425133)
> They said “basically,” so no need to nitpick.
The inflationary use of "infinite" especially in tech crowds that should know better deserves pushback.
There are models of computation that actually model infinite computation. A well-studied one is Büchi automata, basically a generalization of finite state automata to infinite sequences.
> And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?
Nope. You can nest them and for any function that you give you can produce a RE that takes longer than that function to evaluate. (That's literally what "unbounded" means. There is no bound. Doesn't mean it's "infinite". All those computations terminate, which is literally what "finite" means in this context.)
Which is why the "RE" in the article is excrutiatingly slow, given that it needs to perform insane amounts of backtracking. In contrast, "real" regular expression checkers run in linear time.
Also, nitpicking, but they take unbounded time. It's still finite.