checking configuration history of Turing machine using PDA

Question

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

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$.