[eru]

Humans are able to check whether a string of parens, like ()(()()), is matched but finite state machines can't.

In any case, if you know how the regex is constructed, it's not surprising. But I found it fun to actually do the construction, instead of just being theoretically aware of the possibility.

[lifthrasiir]

Is this balanced or not: ((((((((((((((((((((())))))))))))))))))))? Humans can check only so many parentheses before losing track of them, so it is still an FSM in my opinion.

Also, those regexes are directly translated from the equivalent and much smaller FSM. Regexes are necessarily complex only because they have Kleene stars and nothing else; it's like representing every Boolean circuits with NAND, which is of course possible and a little fun fact but the process itself isn't exactly fun to me.

[Thiez]

Humans can't see the balance at a glance, but we can still easily check the balance of arbitrarily complex nested parenthesis because we are not limited in the same way an FSM is. We're just way way way slower than a computer.

[lifthrasiir]

Yeah, I agree that humans can indeed check some non-regular languages. That doesn't however mean that humans are inherently capable for checking all non-regular languages, as they are severely limited in the working memory size. Most if not all divisibility rules are a set of least significant digits or weighted running sums because they are subject to the same constraint, so they are indeed necessarily regular.

[eru]

It all depends on what assumptions you are making. And what model you want to use. (In some sense, as far as we can tell, the entirely visible universe can only contain a finite amount of information. But it still makes more sense most of the time to talk about real world computers as if they implement something like eg a RAM machine or lambda calculus.)

Regular languages admit words of arbitrary length. Eg a regular language can tell you whether 461523850177206879302813461556288524354486376376930935555512181511680646984669431923718933249775297346246192616509695718413981019441670321942082230577379960485875768935619924872490629853314107285524330300421382702242540015152210668552218484465230532702298574921915359545891160565971424053668201732275877291369 is divisible by 7. But a human would have a harder time with this than with the paren example given by the grandfather comment.

[Thiez]

I'll happily admit that there is (to me) no reason to believe that humans can do things that a Turing machine could not, or that we are magically exempt from stuff like the halting theorem or have special insights in NP-complete problems. I am only arguing that we are unarguably more powerful than FSMs, and with some pen and paper (or perhaps an endless string of tape...) we are not as limited by our working memory size. But we are very slow.

[jerf]

These sorts of power discussions require a certain amount of grace, unless you're really just super, super excited to read several paragraphs of intensely mathematical caveats, not just from the first poster, but from every poster in such a thread. There is a reasonable sense in which we can say with a straight face that humans are more powerful than finite state machines, even though in principle a human's entire life, all possible choices and all possible outcomes, could be encoded into some hypothetical state machine. If you want the really good philosophical bones, consult https://www.scottaaronson.com/papers/philos.pdf . Such a hypothetical state machine would require an exponential amount of power to construct (and given the sizes in question, we need not even specify what we mean by "power" since it's exponential in energy, exponential in mass, exponential in "math elements", it'll catch up to you no matter what you're tracking in), whereas we can say with a straight face that a human can increment and decrement a parenthesis count fairly trivially to a high degree (even if there may be error) whereas a finite state machine must give up at some point at some finite depth, and moreover, as you add depth to the state machine it rapidly expands in size whereas the parentheses counter is only tracking an int, which is growing at most log on the number of parenthesis count and thus often reasonably treated as constant for any reasonable problem size.

[eru]

A parenthesis counter that's limited to, say, 1024 bits for its count, is still a finite state machine and can be implemented in those 1024 bits (plus a few extras for book keeping, I guess).

You don't need to have every state in an FSM be explicitly constructed up-front.

The pdf you mention is great, btw.