СИГНАЛИЗИРУЮЩАЯ ФУНКЦИЯ
— функция, характеризующая сложность работы автомата. Напр., в случае Тьюринга машины, С. ф. является ф-ция, которая для каждого значения аргумента равна числу тактов работы, затраченных машиной для получения результата (временная С. ф.) или числу ячеек ленты, в которых хотя бы раз за время работы побывала головка
машины Тьюринга (емкостная С. ф.). С каждым конкретным автоматом можно связать много различных С. ф. См. также
Сложность вычислений.