СЛОЖНОСТЬ ТЬЮРИНГОВЫХ ВЫЧИСЛЕНИЙ

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