Hacker News Reader

Comment by retrac | Hacker News Reader

> Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers).

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.

Informally, regular expressions like in Perl are a kind of string rewriting. And many string rewriting rules, if they can be iteratively applied, are Turing-complete (with the usual caveat about infinite storage and time). The usual definition of a regular expression excludes that kind of iterative application, though. It's just a matching pattern; rewriting is technically outside of the concept of a regular expression.

View on HN

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

Right. And if you really want to push that argument further then there are numbers for which your machine can't decide whether they are prime or not. Most of them, in fact, i.e., for all but a finite number of primes and non-primes, your machine can't tell.

For the theory of computability, this is not a useful model. Neither for complexity theory. Statements like "My machine can sort in constant time" which is arguably true but not useful either. It only holds up to a certain collection size which in a sense makes it both nonsensical and useless. Even concepts like the Chomsky hierarchy with context free languages being one of the prominent components make little sense as long as your computational model is finite state.

Instead, we model them as unbounded, to be able to differentiate between classes of computation problems as well as reason about complexity. The Turing Machine is one of the simple and elegant models, but there are others for other purposes.

I wish that basic education about the theory of computation would stress more why theory treats things like this, to avoid this kind of confusion. (And then people would need to take those classes as well, and not just claim they can write React apps just fine without a degree.)

> And then people would need to take those classes as well, and not just claim they can write React apps just fine without a degree.

Weird tangent. They can write React apps without a degree, can't they? What's wrong with that?

The amount of complexity reasoning you need for something like that is around "this part seems slow, maybe there's a better algorithm somewhere" or "that's a lot of nested loops, maybe I can do with less". Knowing more might help in some pretty rare cases but doesn't seem like a requirement. On the other hand, knowing the complexity of all algorithms and blindly assuming "good complexity = good performance" while never checking is a recipe for desaster.

> On the other hand, knowing the complexity of all algorithms and blindly assuming "good complexity = good performance" while never checking is a recipe for desaster.

Exactly. That's the difference between an actual education and having looked up some Big-O notation on Wikipedia.

> 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

Come on, can we drop this useless trivia that floats around? No, computers are Turing-machines for all practical purposes and no the memory is not the tape, unless your computer is sandboxed from everything. As soon as it has some side effect channels, its “tape” can be as large as needed. For example, it can use the internet to store petabytes of state. But if we want to be more pedantic, it can control and observe physical things, making the whole universe its state space.

Which is still finite, so yeah, even more pedantically you are right due to mathematical infinity not existing, but the actual distinction of a Turing machine is “lazy”, if you don’t hit the limit, you may as well reason as if it were a Turing machine.

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

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

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

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.

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.

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

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.

No, you could create arbitrarily large FSMs, but there are no infinite finite state machines.

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.

The important point here was given infinite space.

Personally, I use "regex" for the informal string-matching/rewriting engines found in most languages and "regular expression" for the formal definition.

By which, of course, this submission title is a lie.

I don't think the GP is the original poster, so them claiming how they "personally" differentiate between the two does not make the submission title a lie.

We don't know how original poster differentiates.

A finite self referential algorithm that checks all numbers for being prime does exist. Running it on a finite computer will eventually hit the bounds of the computer, but that is a limitation outside of the algorithm.

A finite regular expression that checks all numbers for being prime cannot exist already in principle.

Reply on news.ycombinator.com