Алгоритмы и рекурсивные функции

Abstract

Данная книга посвящна систематическому изложению теории алгоритмов и рекурсивных функций. В начальных главах указываются точные определения различных классов рекурсивных функций, доказываются фундаментальные свойства этих классов и строятся примеры рекурсивных функций, обладающих рядом особо важных свойств. В последующих главах рассматриваются классы алгоритмов, достаточные для вычисления произвольных рекурсивных функций и связанные с так называемыми машинами Тьюринга-Поста. Несколько параграфов посвящены приложениям теории алгоритмов к алгебре (проблема эквивалентности слов в конечно определенных полугруппах), математической логике (тождественно истинные формулы языка 1-й ступени) и теории чисел (проблема разрешимости диофантовых уравнений). Книга возникла из курса лекций, читанных автором в Новосибирском университете. Она может служить пособием при первоначальном изучении предмета. В книге содержится много дополнительного материала, появившегося в журналах лишь в последние годы. Это может сделать ее интересной и для аспирантов и научных работников, занимающихся как математической логикой, так и ее приложениями в математике, теории программирования, математической лингвистике и в других смежных областях науки.