Конструктивная функция
- Функция f от натуральных чисел к натуральным числам называется строящейся во времени, если f (n) может быть построена из n машиной Тьюринга за время порядка f (n).
- Существует два определения функции, зависящей от времени: конструируемая по времени и полностью зависящая от времени.
- Функция f называется конструируемой по времени, если существует машина Тьюринга M, которая останавливается через f(n) шагов для всех n ≥ n0.
- Функция f называется полностью зависящей от времени, если существует машина Тьюринга M, которая останавливается через f(n) шагов.
- Пространственно-конструктивные определения включают в себя построение функции в пространстве с использованием O(f(n)) ячеек.
- Примеры функций, которые могут быть построены во времени и пространстве: n, nk, 2n.
- Функции, зависящие от времени, используются в теории сложности, например, в теореме о временной иерархии.
Полный текст статьи: