Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
If we can make memory infinite, why don't we just give Deterministic Finite Automata an infinite amount of states? Why is it useful to define Turing machines and pushdown automata?
Bonus question: Can we think of the universe as a big ass DFA? (Standart Model, interaction of particles, etc.)
Sorry for the long list of questions. I am curious about this topic and I found these questions related.
DFAs have a bounded amount of memory. In contrast, PDAs and Turing machines can use an unbounded amount of memory. The amount of memory used by a PDA or a Turing machine at any given time is finite, but is not necessarily bounded.
For example, the standard PDA for the language of all words of the form $a^nb^n$ uses $\Theta(n)$ memory. In contrast, a DFA uses at most $C$ memory, where $C$ is some constant which depends on the DFA but not on the input.
Most accounts of the physical world involve real numbers having infinite precision. In order to represent these exactly you truly need an infinite amount of memory.
Finite automata can have any amount of memory, but it will always be finite. Pushdown automaton and Turing machine do have unbounded memory at their disposal.
Apart from that, the Turing machine concept is an answer to the question what is an algorithm. In the same way the equivalence between context-free grammar and push-down automaton has taught us about the relation between recursion and stack computations.
One can turn the question around and ask What is the point of finite automata? as Turing machines are more powerful? The answers to that question are enlightening and tell us that each model comes with suitable concepts and properties.
