Re:A regular expression to check for prime numbers
by dheera on Wednesday June 21, 2023 @02:01AM
(#36414940)
If you have an infinite stick of RAM, regular expressions wouldn't be FSMs, either, they could have infinite state space. They would terminate in finite time that is exponential in the size of the prime but nevertheless would still halt.
[ Parent
| on HN ]
Re:A regular expression to check for prime numbers
by umanwizard on Wednesday June 21, 2023 @02:49AM
(#36415221)
The point being made is that “regular expressions”, in the original CS meaning, do not have stack space or anything analogous. “Regular expressions” in modern programming practice are often different and more powerful, of course.
Re:A regular expression to check for prime numbers
by kaba0 on Wednesday June 21, 2023 @05:57AM
(#36416553)
A finite state machine can’t have infinite state space.. also, you can write a finite Turing program that does exactly that, but you can’t write a finite description of an “infinite” state space, which is the whole point.
Ad absurdum everything would be computable (recognizable) by FSMs, simply by listing all the infinite number of possibilities. listOfAllPrimes.concat(“|”), here you are..
Re:A regular expression to check for prime numbers
by funcDropShadow on Wednesday June 21, 2023 @09:53AM
(#36418484)
No, you could create arbitrarily large FSMs, but there are no infinite finite state machines.