Semi-decidable problems with linear bound

Take a semi-decidable problem and an algorithm that finds the positive answer in finite time. The run-time of the algorithm, restricted to inputs with a positive answer, cannot be bounded by a computable function. (Otherwise we’d know how long to wait for a positive answer. If the algorithm runs longer than that we know that the answer is no and the problem would be solvable.)

My question is now: Can such an algorithm still have a, say, a run-time bound linear (polynomial, constant,...) in the input size, but with an uncomputable constant? Or would that still allow me to decide the problem? Are there example?

migrated from cstheory.stackexchange.comJun 20 '12 at 16:58

This question came from our site for theoretical computer scientists and researchers in related fields.

• What's an "uncomputable constant"? A constant is just one number, and thus is a finite amount of information, and thus is trivially "computable". We normally talk about families of problems being computable or uncomputable, not values. – Ben Jun 21 '12 at 12:53
• I guess what I mean is a constant that is unknown, and where the problem of deciding whether a given number is the constant in question is undecidable. According to Raphaels comment, this is not what “computable” means. I wonder if I should fix the question, but fixing it would basically answer it... – Joachim Breitner Jun 21 '12 at 19:10

For your sketched decision algorithm to work, it is sufficient that the run-time is majorized by a computable function. Every linear function $n \mapsto c\cdot n$ even for non-computable c is majorized by a computable function, viz., $n \mapsto \lceil c \rceil \cdot n$. Thus the answer to the question is no: a semi-decision procedure for an undecidable problem cannot have linear run-time (or a run-time majorized by any computable function.)
• @JoachimBreitner: That's the "$\pi$-paradoxon": the existence of a computable majorizing function is enough (for the existence of a decision procedure). We don't have to be able to write it down. – Raphael Jun 21 '12 at 8:33
No, you cannot bound it. Assume you have a characterization of your bound, in terms of a function. That can be a polynomial, exponential, linear etc. We will denote that function by $f(n)$. Since we work on a deterministic setting, we can define an appropriate class $DTIME(f(n))$. Here note that we get a bound on the number of steps which will be a natural number whereas the bound might be not. We can get past such technicalities as @Jan Johannsen describes in his post. What is important is that all deterministic classes are closed under complement, thus all problems in them are decidable. Thus, so will be the semi-decidable problem under consideration, a contradiction.