4 ms·

> The machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. I'm n

> The machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. I'm not sure how that's relevant. Even given infinite space, there still wouldn't exist a Regular Expression (the CS kind) you could write down in finite time that would match only primes. At least IIRC, it's been a 20+ years since I last took a Discrete Math course :)

dheera 3y ago
> Even given infinite space, there still wouldn't exist a Regular Expression (the CS kind) you could write down in finite time that would match only primes. The point is, neither would there exist a non-(Regular Expression) method that could do such, if you're running it on a finite state machine (your computer).
- tylerhou 3y ago
  But that argument is not interesting. "We can't count arbitrarily high because the universe is finite." Yeah, duh. (Observable universe, for the pedants.) It's more interesting to ask: suppose you did have a magical stick of RAM that had infinite storage, and suppose you augmented your computer to store and query that memory. Then -- yes -- your computer could determine whether any number, however large, is prime. An FSM could not.
  - dheera 3y ago
    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.
    - School-Cotton 3y ago
      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.
    - kaba0 3y ago
      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..
    - funcDropShadow 3y ago
      No, you could create arbitrarily large FSMs, but there are no infinite finite state machines.
- lapinot 3y ago
  The important point here was given infinite space.
- kaba0 3y ago
  There is, the property of being a Turing machine would only be thrown out when you actually hit the limit. Besides computers being able to modify state not only in their memory but e.g. outside memory, I can also look at my computer as a lazy-taped Turing machine that chugs along writing only to its memory, and when it were to go off it pauses and waits for me to add additional memory. This is just useless pedantism that diminishes the very imporrant categorization of Chomsky.
School-Cotton 3y ago
> At least IIRC, it's been a 20+ years since I last took a Discrete Math course :) Your memory is correct and there is very simple intuition for this. Regular languages are those that can be matched by a machine with bounded memory. So, let's say that bound is "n" bits. Then your machine will not be able to read in unary strings larger than 2^n.

dheera 3y ago

> Even given infinite space, there still wouldn't exist a Regular Expression (the CS kind) you could write down in finite time that would match only primes. The point is, neither would there exist a non-(Regular Expression) method that could do such, if you're running it on a finite state machine (your computer).

tylerhou 3y ago
But that argument is not interesting. "We can't count arbitrarily high because the universe is finite." Yeah, duh. (Observable universe, for the pedants.) It's more interesting to ask: suppose you did have a magical stick of RAM that had infinite storage, and suppose you augmented your computer to store and query that memory. Then -- yes -- your computer could determine whether any number, however large, is prime. An FSM could not.
- dheera 3y ago
  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.
  - School-Cotton 3y ago
    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.
  - kaba0 3y ago
    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..
  - funcDropShadow 3y ago
    No, you could create arbitrarily large FSMs, but there are no infinite finite state machines.
lapinot 3y ago
The important point here was given infinite space.
kaba0 3y ago
There is, the property of being a Turing machine would only be thrown out when you actually hit the limit. Besides computers being able to modify state not only in their memory but e.g. outside memory, I can also look at my computer as a lazy-taped Turing machine that chugs along writing only to its memory, and when it were to go off it pauses and waits for me to add additional memory. This is just useless pedantism that diminishes the very imporrant categorization of Chomsky.

School-Cotton 3y ago

> At least IIRC, it's been a 20+ years since I last took a Discrete Math course :) Your memory is correct and there is very simple intuition for this. Regular languages are those that can be matched by a machine with bounded memory. So, let's say that bound is "n" bits. Then your machine will not be able to read in unary strings larger than 2^n.