0
$\begingroup$

Can a pushdown automaton solve the halting problem for another Pushdown automaton? It's already shown here turing machine can solve the halting problem for a pushdown automaton. Decidability of halting problem for DPDAs with $\epsilon$-transitions? But can a pushdown automaton do the same?

$\endgroup$
3
  • $\begingroup$ What is the “halting problem” in case of DPDA? It always halts. $\endgroup$ – prime_hit Jun 9 '20 at 18:16
  • $\begingroup$ I suspect you'll have to define how you propose to represent pushdown automata before the question becomes answerable. Because PDAs are so weak, this question might be sensitive to the specific representation used. $\endgroup$ – D.W. Jun 9 '20 at 19:54
  • $\begingroup$ The halting problem only makes sense when considering machines that don't always halt. Pushdown automata always halt by definition. They either accept or reject. $\endgroup$ – frabala Jun 9 '20 at 20:40

Your Answer

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

Browse other questions tagged or ask your own question.