Efficiently deciding whether TM accepts all inputs in at most $k$ steps

Question

I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q_s, q_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then the positions $A$ can reach are limited by $2k$. Thus I can create a NFA with state set:

$$ Q' \subseteq \{1,\dots,k\} \times Q \times \varGamma^{2k} \times \varGamma \times \{-k,\dots,k\} $$

which keeps track of all necessary information to simulate $M$ with a suitable transition function. This construction is exponential in $k$ and I wonder if this can be avoided by using a PDA. Does the stack give ma enough information to avoid this exponentail blow up?

Answer 1

Given a 3CNF formula on $n$ variables, we can construct in polynomial time a Turing machine with polynomially many states $a(n)$ that accepts a truth assignment and in polynomial time $b(n)$ checks whether it satisfies the formula, and if so, enters an infinite loop. If you believe ETH, then checking whether this machine halts on all inputs in $b(n)$ steps should take time $2^{\Omega(n)}$, indicating some kind of exponential blow-up.