> I think our disagreement between these is mostly semantics Yes. I agree. > Finite state machines can do anything that requires a finite amount of memory. F

> I think our disagreement between these is mostly semantics Yes. I agree. > Finite state machines can do anything that requires a finite amount of memory. For example, finite state machines can't recognize balanced parentheses. But they can recognize balanced parentheses in strings of length up to 10. I already typed something similar before I changed my comment. I basically wanted to argue that it's theoretically correct, but we even dismiss it in computation theory, because modeling every state of a turing machine with just a few kilobyte of input is physically impossible. But I was so unsure if that was actually true or there was a more fundamental problem that I convinced myself the "finite input" isn't the only thing that limits the capabilities of finite-state automatons vs pushdown automatons vs turing machines. I'm still not entirely sure, but I was thinking exactly the same as you explained.