Предположим, что для каждого существует машина Тьюринга которая определяет язык во времени . Существует ли единственный алгоритм, определяющий во времени ? (Здесь член измеряется через , длину ввода.)
Имеет ли значение, если алгоритмы вычислимы или эффективно вычисляются в терминах ?
Мотивация: во многих доказательствах легче построить алгоритмы времени чем ограничивающий алгоритм . В частности, вам нужно ограничить постоянный член в чтобы перейти к пределу . Было бы неплохо, если бы был какой-то общий результат, который вы можете вызвать, чтобы перейти к пределу напрямую.
источник