3 ms·
Neat observation: finite automata, push-down automata, and Turing machines can be distinguished purely by the number of stacks they need. Finite automata: no s
by mcguire 2y ago
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.)
- mark_undoio 2y agoI 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.
- mcguire 2y agoThat was the way I learned it. I found the lambda calculus the odd one out. :-)