For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space.But what about PDAs with $\epsilon$-transitions?  Is the halting problem decidable for deterministic PDA's with $\epsilon$-transitions?  Given such a DPDA $P$ and an input $x$, can we decide whether $P$ will halt on input $x$?The stack may be infinitely large, so it seems like it might be much harder here to see if the PDA is in an infinite loop or not. I don't think it's as easy as answered here for non-$\epsilon$ PDAs:[For] DFAs or PDAs, the halting problem is decidable: the machine  always halts because it halts when it reaches the end of its input,  the input is finite and the machine consumes one character of input at  every step.Is the halting problem specific to Turing machines?)The answer to my earlier question (Is a PDA's stack size linear bounded in input size?) also seems to point in a direction of a higher difficulty of proving this.
Decidability of halting problem for DPDAs with $\epsilon$-transitions?
decision problem;pushdown automata;halting problem
The halting problem is decidable; use memoizationFor DPDA's, you can prove directly that the halting problem is decidable, without too much work.In particular, say that the DPDA has a cycle starting at state $q$ and a stack symbol $\alpha$ if and only if there's a non-empty sequence of $\epsilon$-transitions that start at a configuration with state $q$ and with $\alpha$ at the top of the stack and end at a similar configuration (with state $q$ and with $\alpha$ at the top of the stack, though the rest of the stack can be different).  Then we have:Theorem.A DPDA enters an infinite loop on input $x$ if and only if it reaches a configuration with state $q$ and stack symbol $\alpha$ on the top of the stack such that there's a cycle starting from $(q,\alpha)$.  Otherwise, it halts on input $x$.It is easy to test whether there exists any such state $q$.  Just build a graph with vertex set $Q \times \Gamma$ and with an edge $(q,\alpha) \to (q',\beta)$ whenever there is an $\epsilon$-transition between the two, i.e., iff $\delta(q,\epsilon,\alpha)$ contains an element of the form $(q', \beta s)$.  You can find all self-cycles in this graph by straightforward analysis of the graph (e.g., decomposition into strongly connected components, and returning all $(q,\alpha)$ that are in a SCC of size $>1$ or have a self-loop back to themselves).Next, given an input $x$, you can test whether the DPDA ever reaches any such $(q,\alpha)$ by standard methods.Memoization. Another way to put this is: use the obvious algorithm for simulating the DPDA, but memoize it.  Keep track of each pair $(k,q,\alpha)$ that has been reached during the simulation, where $k$ denotes the number of letters of $x$ read so far and $q$ denotes the current state of the DPDA and $\alpha$ denotes the symbol on the stack of the stack.  If you ever see a pair $(k,q,\alpha)$ that is encountered twice, then you know that the DPDA enters an infinite loop, and you can immediately return does not halt on input $x$.  If you never see any such pair twice, then eventually the algorithm will return: its running time will be bounded by the length of $x$ times the number of states of the DPDA times the number of stack symbols of the DPDA, and in particular this algorithm will terminate.This gives a decider for the halting problem for DPDAs.Another viewpointGiven a PDA $P$ and an input $x$, you can efficiently test whether $x$ is accepted by $P$.  This can be done in time polynomial in the length of $x$ and the size of $P$.  In particular, this is a terminating computation, so that means that the acceptance problem (given $P,x$, does $P$ accept $x$?) is decidable for PDA's.Here is one way to see how.  Let $X$ denote the language containing only $x$, i.e., $X=\{x\}$.  $X$ is finite, so it is regular.  Now the intersection of a context-free language with a regular language is also context-free, so $L(P)\cap X$ is context-free.  You can test whether a context-free language is empty or not in polynomial time.  So, test whether $L(P) \cap X$ is empty or not; this tells you whether $P$ accepts $x$ or not.This holds even for non-deterministic PDAs.Now, suppose we take a DPDA $P$, and modify it to transition to some new state $q_\text{final}$ if and only if it would halt (this can be done).  Mark $q_\text{final}$ as an accepting state and all others as non-accepting, so it accepts by accepting state and accepts iff it reaches state $q_\text{final}$.Then, test whether the modified PDA accepts the input $x$.  By the above, this is decidable (and computable in polynomial time).  This tells us whether the original PDA halts on input $x$.Bottom lineThe halting problem for DPDAs is not only decidable; it is computable in polynomial time.