Determining whether a Turing machine halts within k steps is computable: https://math.stackexchange.com/questions/3370296/halting-problem-within-a-finite-time-i

Determining whether a Turing machine halts within k steps is computable: https://math.stackexchange.com/questions/3370296/halting-problem-within-a-finite-time-interval https://math.stackexchange.com/questions/3370296/halting-pro... If the number of steps is specified in unary, then the problem is NP-complete: https://www.ics.uci.edu/~eppstein/161/960312.html https://www.ics.uci.edu/~eppstein/161/960312.html