checking configuration history of Turing machine using PDA I am trying to understand the technique of using configuration history in proofs.
To prove that:
$\{&lt;M&gt;|M\,\,\,is\,\,\,a\,\,\,TM\,\,\,and\,\,\,L(M)=\sum^* \}\notin RE$
given $&lt;M,w&gt;$ we have built a Turing machine that accepts all words except M accepting configuration on w. (and then simple reduction)
To prove that:
$\{&lt;P&gt;|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
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$.