5

(Note: To avoid complications, my Turing machines always have to move either to the left or to the right; they cannot remain in place. Not using this convention makes the proofs a bit more cumbersome, but doesnt change anything meaningful.)
Theorem: The problem "Given a TM $T$ and an input $w \in...