# Automata

## Finite state automata

## Pushdown automata

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