I meant, given a turing machine, judge whether a pushdown automaton will halt.

Pushdown automaton: a finite state machine with a stack

If so, is there any unsolvable problem weaker than halting problem?


Yes, the halting problem for PDAs is decideable. The current snapshot of a PDA is determined by: the unread symbols in the input, the state of the deterministic control, the symbol on top of the stack.

Here's a two-tape TM that decides whether a PDA $P$ will halt on input $x$:

  1. The input $x$ is written on the first tape.

  2. The machine simulates the PDA using the first tape for storage. In particular, the first tape will contain the input $x$ (the machine erases the input symbols as it reads them), the current state of the PDA's finite control, and also a list of all symbols on the simulated PDA's stack.

  3. After it simulates a step of the PDA, the TM appends the current snapshot of the PDA onto the second tape. It copies over the remaining input, the current state, and the symbol at the top of the stack.

    So the second tape contains a list of every snapshot that the PDA has ever been in.

  4. Every time the TM copies over a new snapshot, it should check to see whether that exact snapshot has occurred on the tape already. If it has, the PDA has entered into a loop and will never halt. The TM should reject.

  5. The PDA will either halt within finitely many steps, or will loop forever. There are $Q\times n \times \Gamma$ possible snapshots, where $Q$ is the current PDA state, $n$ is the number of symbols in the input, and $\Gamma$ is the number of symbols in the stack alphabet. For this reason, the machine will either halt within $Q\times n\times \Gamma$ steps, or (by the pigeonhole principle) loop forever. The problem is therefore decideable.

| cite | improve this answer | |
  • $\begingroup$ Does the checking only see the first k chars? $\endgroup$ – l4m2 Mar 20 '18 at 10:48
  • $\begingroup$ The snapshot which the TM reads consists of the remaining input, the current state of the PDA, and the top symbol on the stack. That's enough to decide whether the machine will loop, because that info is what the PDA uses to decide what to do next. $\endgroup$ – user326210 Mar 20 '18 at 16:21
  • $\begingroup$ What if there's a loop which takes one symbol from the stack per loop? $\endgroup$ – l4m2 Mar 21 '18 at 4:05
  • $\begingroup$ @l4m2 Is that a problem? $\endgroup$ – user326210 Mar 21 '18 at 4:15
  • $\begingroup$ It makes you judge it as an infinite loop while it actually halt $\endgroup$ – l4m2 Mar 21 '18 at 4:19

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.