Are there decidable problems such that for no algorithm which solves the problem we can give a time bound as a function of the length n of the input instance?
I arrived at this question because I was thinking about the following:
Assume we have a recursively enumerable, but undecidable problem. Assume further that I is a "yes"-instance of the problem. Then for no algorithm which identifies the "yes"-instances of the problem we can give a time bound in terms of the size n of I. For if we could give such a time bound, we could decide the problem, as we could simply conclude that I is a "no"-instance when the time bound is exceeded.
Since we cannot give a time bound for recursively enumerable, undecidable problems (for the computation time for "yes"-instances), I was wondering if there are decidable problems as well for which we cannot give a time bound.