В книге представлены основные классы "элементарных" рекурсивных функций, изучаемых в теории рекурсивных функций. Приведены различные определения исследуемых классов, установлены соотношения включения между ними. В терминах сложности вычислений получено описание большого числа классов элементарных функций. Для ряда классов дано решение проблемы о существовании конечных базисов по суперпозиции.Книга ориентирована на широкий круг читателей: студентов и аспирантов математических факультетов, изучающих теорию алгоритмов, а также научных сотрудников и преподавателей высшей школы.
V knige predstavleny osnovnye klassy "elementarnykh" rekursivnykh funktsij, izuchaemykh v teorii rekursivnykh funktsij. Privedeny razlichnye opredelenija issleduemykh klassov, ustanovleny sootnoshenija vkljuchenija mezhdu nimi. V terminakh slozhnosti vychislenij polucheno opisanie bolshogo chisla klassov elementarnykh funktsij. Dlja rjada klassov dano reshenie problemy o suschestvovanii konechnykh bazisov po superpozitsii.Kniga orientirovana na shirokij krug chitatelej: studentov i aspirantov matematicheskikh fakultetov, izuchajuschikh teoriju algoritmov, a takzhe nauchnykh sotrudnikov i prepodavatelej vysshej shkoly.
