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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ This is the bounded halting problem. $\endgroup$ – Raphael♦ Oct 18 '16 at 14:50
Add a comment
|
$\begingroup$
$\endgroup$
3
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.
-
$\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
