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