Начальные понятия дескриптивной теории алгоритмов. Лекция 1 // Успенский В. А.

В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть: конструктивный обьект, алгоритм, число шагов алгоритма, вычислимая функция, перечислимое множество, разрешимое множество, сводимость нумераций, главная вычислимая нумерация, вычислимая операция. Успенский Владимир Андреевич, доктор физико-математических наук, профессор. Летняя школа «Современная математика», г. Дубна, 20 и 22 июля 2009 г.