1
$\begingroup$

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.

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for the answer! Do we really need infinite precision to calculate the states of the universe? I heard that the Planck length is the smallest meaningful length and the universe might be discrete. For example, the position of an electron, etc. I am a beginner in quantum physics and physics in general. So sorry if my questions don't make sense. $\endgroup$ May 15 at 18:34
  • $\begingroup$ Unfortunately I'm not a physicist, so I can't help you with that. $\endgroup$ May 15 at 21:07
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.