I am trying to understand the technique of using configuration history in proofs.

To prove that: $\{<M>|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$

given $<M,w>$ we have built a Turing machine that accepts all words except M accepting configuration on w. (and then simple reduction)

To prove that: $\{<P>|P is\,\,\, a\,\,\, PDA\,\,\, and\,\,\, L(P)=\sum^*\}\notin RE$

we showed the same proof, only that we built a PDA that accepts all the words except the accepting configuration of M on w.

Does PDA's ability to determine whether input is an accepting configuration of M on w actually means that I can simulate M's run on w with a PDA? Or testing whether configuration is an accepting configuration is different from a simulation


1 Answer 1


PDAs are strictly weaker than TMs. For instance, PDAs always halt after precisely $|w|$ steps, but there are algorithms (aka TM) for questions that take more steps than that.

sorting an array for example, would take definitely more than $\Omega(|w|log(|w|))$ which is larger than $|w|$ at some point.

It cannot simulate running a machine on a word as it simply takes more time! Checking configuration history takes less time because it's length is proportional to the running time of $M$ on $w$.

  • $\begingroup$ got it. thank you!! $\endgroup$
    – Ella
    Jun 20, 2020 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.