Can I write a Finite Automaton to do anything a Full-Featured General Purpose Computer can do?
Your computer is a finite automaton. It's state can be uniquely described by the content of its registers, RAM, SSDs, etc. Every input (including the system clock) causes a transition from one state to the next, in a deterministic manner. Conceivably, you could enumerate all the possible states, and draw the arcs between them, forming a deterministic finite automaton (DFA). There are maaaaany states, but they are finite.
However, this only works because the infinite memory requirement of Turing machines (TMs) is often ignored (exactly because it would never be achievable, so it's of little pragmatic use).
Pushdown automata (PDAs) and TMs can be thought to have two separate components.
- A "decision making" part, that decides how one state should transition to a next, analogous to a CPU.
- In a PDA, this is the automaton
- In a TM, it's the rule set by which symbols are evaluated
- They also have a "working memory", whose job is to contain most of the state of the system, analogous to RAM.
- In a PDA, this is the push-down stack
- In a TM, it's the tape
DFAs have both of these components rolled into one. The automaton is responsible both for all decision making, and for all state-keeping. As a consequence, the state can never be bigger than the DFA.
There is an asymmetry here: PDAs and TMs are granted use of infinite storage (bottomless push-down stacks, infinite tapes), whereas DFAs are not, by definition. If a DFA was given the same affordance for infinite state-keeping (by allowing it to have infinite states), it would no longer be a deterministic finite automaton. It would be a deterministic infinite automaton!
Interestingly, infinite state-automata are not only Turing Complete, but they're actually more powerful than Turing Machines. With infinitely many states allowed, any langauge can be expressed as an automaton with one start node, one accepting state, and one non-accepting state. For every string in the language, an arc is made to the accepting state. For every other string, an arc is made to the non-accepting state.