4 ms·
They said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?
by petters 3y ago
They 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.)