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?

  • 1
    $\begingroup$ 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. $\endgroup$
    – Discrete lizard
    May 21, 2019 at 12:19
  • $\begingroup$ Was a mistake, could not undelete sorry! $\endgroup$
    – Cilenco
    May 21, 2019 at 17:16

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.