70.4k views
5 votes
Difference between pushdown automata and turing machine

User Gorky
by
7.8k points

1 Answer

4 votes

Answer:

A push down automata is a type of automata that can only access the top of its stack, whereas a Turing machine can be used to access an infinite tape1. If a push down automata contains more than one stack, it is known as a Turing machine1. One Turing machine is more powerful than one pushdown automaton, as the halting problem for Turing machines is undecidable2

Step-by-step explanation:

User Rohin Sidharth
by
7.4k points