[finitemonkey]

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

They said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?

[finitemonkey]

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

[cubefox]

I think with "unbounded but finite" he meant potential infinity rather than actual infinity.