Понятие алгоритма становится в настоящее время одним из важнейших понятий как теоретической, так и прикладной математики. Это связано в первую очередь с современным развитием электронной вычислительной техники и необходимостью создания мощного математического обеспечения для этой техники. Немаловажными являются и связи теории алгоритмов с математической логикой и основаниями математики; точное математическое определение понятия алгоритма впервые было найдено в рамках формальных систем математической логики. Теория рекурсии — так называется этот третий том «Справочной книги по математической логике» — составляет теоретическую основу современного учения об алгоритмах.
Первая вводная глава этого тома, написанная Эндертоном, човольно подробно и мотивированно знакомит читателя с тем разделом теории алгоритмов, который теперь называется «классической» теорией рекурсии.
Две следующие главы, написанные соответственно Девисом || Рабином, знакомят читателя с постановками различных ал-тритмических проблем, возникающих в арифметике, алгебре, математической логике и других разделах математики. Наряду г формулировками проблем здесь имеются указания на методы решения таких проблем и даны примеры. Следует отметить, что "••с эти главы не могут служить обзорами по рассматриваемой проблематике, так как отбор материала в этих главах отражает ниюльно субъективные взгляды авторов, не заботившихся, портимому, ни о достаточно полном обзоре результатов, ни о точности указаний на авторство приводимых утверждений. Советскому читателю, заинтересовавшемуся алгоритмическими про-ь'И'мами, можно рекомендовать ознакомиться с обзорами I p hi о в а, Лаврова, Тайманова и Тайцлина [1], Ко -i и р и н а и П и н у с а [1] и с книгой Е р шо в а [1].
Четвертая глава, написанная Симпсоном, знакомит читателя • пинии из наиболее развитых разделов собственной (внутренне и) теории алгоритмов — теорией (тьюринговых) степеней не-1'.м|нчнимости. Обзор результатов довольно полон и хорошо на-нin an. Для читателей, желающих познакомиться с результатами ■ Фугих степенях неразрешимости (//- и m-степенях), можно рекомендовать недавний обзор Одифредди [1].
