Automata

Finite state automata

• Parity

Pushdown automata

• Matching parens

Turing machines

• Incrementing a binary number
• Doubling a number
• Busy beaver, 3-state, 2-symbol
• Busy beaver, 4-state, 2-symbol - enough tape is provided
• Busy beaver, 4-state, 2-symbol - tape is dynamically extended
• Busy beaver, 5-state, 2-symbol - at least we think so...