Hacker News Reader

Neat observation: finite automata, push-down automata, and Turing machines can be distinguished purely by the number of stacks they need.

Finite automata: no stack.

Pushdown automata: one stack.

Turing machine: two stacks. (Use them like the tape: to move forward, pop the f-stack and push the symbol on the b-stack; to move backward pop the b-stack and push to the f-stack.)

View on HN

I think it's a shame this wasn't highlighted more explicitly in, at least, my computer science degree.

We did finite state machines in quite a bit of detail, vaguely referred to pushdown automata but then concentrated on lambda calculus for quite a lot, with Turing machines less so.

The Turing machine description, without showing it in this hierarchy, seems like a really weird abstraction. Fitting it in here (and combining it with the different Chomsky classes of grammar) makes it all feel more joined up.

That was the way I learned it. I found the lambda calculus the odd one out. :-)

Reply on news.ycombinator.com