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

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?

• Please do not delete your question after you have received a (valid) answer. We do not only want to give you an answer for this question, but also others who may have the same question later. May 21, 2019 at 12:19
• Was a mistake, could not undelete sorry! May 21, 2019 at 17:16

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.