01. Аннотация

Актуальность рассматриваемой методической задачи обусловлена тем, что в учебных планах студентов-программистов существенное место занимает теория алгоритмов, и требуется отработка методики строгого и в то же время доступного студентам, не специализирующимся собственно в математике, изложения основ этой теории.

В статье предлагается методика изложения ключевых положений теории алгоритмов на примере нормальных алгорифмов Маркова. Подробно доказывается алгоритмическая неразрешимость проблемы применимости (или проблемы останова) для нормальных алгорифмов. Кратко излагаются основные результаты, необходимые для понимания основной теоремы. Содержание статьи будет полезно студентам программистских специальностей, а также преподавателям курсов математической логики и теории алгоритмов, курсов проектирования алгоритмов.

Ключевые слова: алгоритм, нормальный алгорифм Маркова, алгоритмически неразрешимые проблемы.

Следующая >