1
$\begingroup$

I can't find the standard name for this problem, so lets call it TIMING, it takes as input a Turing machine $F$ with its input $i$, and a number of steps $n$. It returns yes if $F(i)$ halts in less than $n$ steps, otherwise it returns no. What is the time complexity of this problem in terms of $n$, is it $n\log n$ as it is similar to a universal Turing machine, or does the counting each step mean it takes longer.

$\endgroup$
  • $\begingroup$ This is the bounded halting problem. $\endgroup$ – Raphael Oct 18 '16 at 14:50
0
$\begingroup$

Let S (F, i, n) = the number of steps that F (i) takes until it halts, if it halts in n or fewer steps, and n if F (i) doesn't halt in n steps. Then you can simulate the Turning machine and get the result in O (S (F, i, n)) steps.

If this were important to you, then you could examine a few Turing machines, and see if you can detect patterns in their operation. For example, you might detect a pattern that indicates the Turing machine is trying to add two numbers x and y, and you might be able to analyse how many steps this will take and what state the Turing machine is afterwards; if you do this then you might often get a result in substantially fewer than c * N steps.

Or in your simulation, you might detect that the Turing machine enters the exact same state that it entered before; in that case it won't ever halt.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do you simulate the TM without introducing a slowdown? $\endgroup$ – adrianN Oct 18 '16 at 14:11
  • $\begingroup$ Constant slowdown is fine, because we are looking for O () only. $\endgroup$ – gnasher729 Oct 19 '16 at 7:37
  • 1
    $\begingroup$ I think you have logarithmic overhead $\endgroup$ – adrianN Oct 19 '16 at 7:45

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