Справочная книга по математической логике, Часть 3, Теория рекурсии, Барвайс Дж., 1982.
Понятие алгоритма становится в настоящее время одним из важнейших понятий как теоретической, так и прикладной математики. Это связано в первую очередь с современным развитием электронной вычислительной техники и необходимостью создания мощного математического обеспечения для этой техники. Немаловажными являются и связи теории алгоритмов с математической логикой и основаниями математики; точное математическое определение понятия алгоритма впервые было найдено в рамках формальных систем математической логики. Теория рекурсии — так называется этот третий том «Справочной книги по математической логике» — составляет теоретическую основу современного учения об алгоритмах. Первая вводная глава этого тома, написанная Эндертоном, довольно подробно и мотивированно знакомит читателя с тем разделом теории алгоритмов, который теперь называется «классической» теорией рекурсии. Две следующие главы, написанные соответственно Девисом и Рабином, знакомят читателя с постановками различных алгоритмических проблем, возникающих в арифметике, алгебре, математической логике и других разделах математики. Наряду с формулировками проблем здесь имеются указания на методы решения таких проблем и даны примеры. Следует отметить, что обе эти главы не могут служить обзорами по рассматриваемой проблематике, так как отбор материала в этих главах отражает довольно субъективные взгляды авторов, не заботившихся, по-видимому, ни о достаточно полном обзоре результатов, ни о точности указаний на авторство приводимых утверждений.
