If a language L is decidable, does that imply that the is a computable function f such that L is in O(f(n)) ?
For example what would be the complexity class of the language of "provably halting Turing machines that halt in an even number of steps"
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ A better forum for this question is Theoretical Computer Science. $\endgroup$– Joseph O'RourkeCommented Sep 2, 2013 at 13:10
-
2$\begingroup$ Does "is in $O(f(n))$" mean that deciding whether a string is in $L$ can be computed in time $O(f(n))$ where $n$ is the length of the string? Does the language have a finite alphabet? (If both answers are yes, then the answer is trivially yes by taking $f(n)$ to be the maximum computing time of the decision algorithm over strings of length $n$. This is computable since the alphabet is finite and there are only finitely many strings of length $n$.) $\endgroup$– François G. DoraisCommented Sep 2, 2013 at 13:33
-
1$\begingroup$ @JosephO'Rourke, complexity theory questions are on-topic here at MO. $\endgroup$– Joel David HamkinsCommented Sep 2, 2013 at 13:57
-
$\begingroup$ Ken, I think you mean Turing. $\endgroup$– Joel David HamkinsCommented Sep 2, 2013 at 14:00
-
$\begingroup$ @Joel: Apologies; I stand corrected. $\endgroup$– Joseph O'RourkeCommented Sep 2, 2013 at 14:06
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
The answer to your first question is yes: if $L$ is decidable, there is an algorithm that decides it, and this algorithm has a time complexity which is in $O(f(n))$ for $f(n)=$``maximal running time of the algorithm on entries of length $n$''.
As for your second question, I'm not sure your language is decidable: what would be your algorithm ? Trying all proofs of halting only works if a proof exists, and we'll get stuck if the halting problem for this machine is undecidable. Anyway if an algorithm exists, the above construction for $f(n)$ answers your question.
$\begingroup$
$\endgroup$
The answer to your second question is that this problem is not decidable, since in fact that language is equivalent to the halting problem. First of all, every halting program is provably halting (in very weak systems, such as PA), since the computation itself can be turned into a proof of halting. Another way to say this is that every true $\Sigma^0_1$ assertion is provable. So you are really just asking about the language of programs that halt in an even number of steps. But this is equivalent to the halting problem, since we can reduce the halting problem to it: given any Turing machine program $p$, design a new program $p'$ that operates just like $p$, but inserts a redundant step between each step of $p$. So $p$ halts on a given input if and only if $p'$ halts on that input in an even number of steps. So if we could decide your problem, then we could decide the halting problem.
answered Sep 2, 2013 at 13:56
$\begingroup$
$\endgroup$
Let me add something on the second question. As D K wrote, the way you formulated it it is undecidable. However, if you take a fixed Turing machine $M$ such that a ($\Sigma^0_1$-sound) theory $T$ proves “for every $x$, $M$ halts on input $x$”, then the language accepted by $M$ is indeed decidable, which means there is a recursive bound on its running time. While this is just about everything one can say in general, quite a lot more is known for some particular theories $T$. For example, if Peano arithmetic proves that $M$ halts on every input, then its running time is eventually bounded by a function $f_\alpha$ in the fast-growing hierarchy with $\alpha<\epsilon_0$.
answered Sep 2, 2013 at 13:59