After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my prior question:
- arrive at the same state as you were in previously
- with the same top symbol as you had last time
- without consuming anything on the stack, and
- without consuming any input.
But is my last question actually unanswerable because we cannot, in fact, determine whether a NPDA will halt? Is the halting problem even solvable for NPDAs?