The proof in my textbook, that $E_{TM}$ can be decided by oracle machine $O^{A_{TM}}$, uses a Turing machine $P$ such that for an input $w$:
- $P$ runs the Turing machine $M$ on all strings of $\Sigma^*$
- If $M$ accepts the string, $P$ accepts
$O^{A_{TM}}$ then asks the oracle if $<P,w> \in A_{TM}$
I can't seem to understand why $P$ can run $M$ for all strings of $\Sigma^*$ because this is an infinite amount of strings. I do, however, understand that $P$ actually never has to run and is purely constructed to ask the oracle if it accepts.