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

В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть:

• конструктивный обьект;
• алгоритм;
• число шагов алгоритма;
• вычислимая функция;
• перечислимое множество;
• разрешимое множество;
• сводимость нумераций;
• главная вычислимая нумерация;
• вычислимая операция.

Между этими понятиями существуют соотношения, хотя в большинстве своём и простые, но всегда достаточно глубокие.
В лекции предполагается разьяснить указанные понятия и соотношения.
Предварительных знаний, помимо знакомства с общим представлением о значении слов «множество», «функция», «упорядоченная пара», не требуется.