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

Владимир Успенский

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

* конструктивный объект;

* алгоритм;

* число шагов алгоритма;

* вычислимая функция;

* перечислимое множество;

* разрешимое множество;

* сводимость нумераций;

* главная вычислимая нумерация;

* вычислимая операция.

Между этими понятиями существуют соотношения, хотя в большинстве своём и простые, но всегда достаточно глубокие.

В лекции предполагается разъяснить указанные понятия и соотношения.

Успенский Владимир Андреевич, доктор физико-математических наук, профессор.

Летняя школа «Современная математика», г. Дубна

20 и 22 июля 2009 г.

Источник: vk.com

Комментарии: