3 ms·
> and now they are incredibly powerful but can take basically infinite memory and time. Which is why the "RE" in the article is excrutiatingly slow, given that
by finitemonkey 3y ago
> and now they are incredibly powerful but can take basically infinite memory and time.
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.
- petters 3y agoThey said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?
- cubefox 3y agoI think with "unbounded but finite" he meant potential infinity rather than actual infinity.
- finitemonkey 3y ago> 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.)