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