That argument is theoretically sound, and I've upvoted you for bringing up such a helpful contribution, but it's practically nonsense.
We are all running computers that are finite-state machines: if you have roughly a trillion bits of storage, you can have up to 2^1T states.
For most numbers that are interesting to humans, we are able to test their primality with regular languages, which are detectable by finite-state machines. The number of states might be quite large indeed.
You're mostly right, I made a similar point few months ago[1].
However, I must disagree that we are able to use regular expressions to test for primality all the number we're interested in. Your argument only proves that there exists a regular expression that tests for primality all the numbers below N, where N is arbitratily large. It does not shows any way how to construct it[2], nor does it guarantee that the DFA we will be using to test for primality will fit in available memory.
[2] - It's actually trivial: example regular expression we're looking for is /a^p_1|a^p_2|...|a^p_N/, where p_1, ..., p_N are primes below. Sadly, to use it to test for primality, we need to know if the number is prime beforehand.
Actually, it sounds like an interesting problem -- to come up with an interesting and nontrivial regular expression schema that for every N gives us a regular expression that tests for primeness all numbers less than N.
Come to think of it, the existence of any such interesting schema seems highly unlikely -- the Parikh's theorem implies that the set of lengths of words matched by regular expression (or even context-free grammar) seems to be too constrained to allow for such scheme -- we can easily find non-prime matched by an such regular expression, and Parikhs theorem seems to imply that it is not much bigger than the automaton state count.
The only thing practically nonsense here is viewing a computer as a finite state machine with 2^trillion states! That state machines cannot decide primality is downright practical by comparison.
>We are all running computers that are finite-state machines
The amount of storage of a computer is not fixed, and is easily extendable, and extending memory fits simply in the Turing Model, and does not affect the internal states of the Turing Machine. In contrast, any time a new source of memory is introduced (say, a new hard drive or aws cluster), you'd have to change your DFA, which breaks your statement 'a computer is a DFA'.
I really don't see how calling computers DFA's can in anyway be considered 'practical'.
It's tough to define or predict what is "interesting to humans." I'm interested in primality testing of arbitrarily large integers that wouldn't be feasible to test with a huge regex consisting of a bunch of known primes combined with alternation.
I don't think that solution would be very feasible anyway. The four largest known primes alone would take about 20 megabytes if stored as unsigned integers.
We are all running computers that are finite-state machines: if you have roughly a trillion bits of storage, you can have up to 2^1T states.
For most numbers that are interesting to humans, we are able to test their primality with regular languages, which are detectable by finite-state machines. The number of states might be quite large indeed.