ПРЕДИСЛОВИЕ

Настоящая книга, являющаяся элементарным введением в теорию алгоритмов, посвящена разъяснению одного из самых основных понятий математики — понятия алгоритма; в ней рассматривается круг вопросов, лежащих на грани между математической логикой и теорией автоматических вычислительных машин.

В основу книги легли популярные лекции и обзорные доклады, с которыми автор выступал в г. Пензе, начиная с 1951 года, перед разными аудиториями, а также одноименная статья, написанная им для журнала «Математика в школе» (№№ 4-5, 1956).

Во втором издании книги значительно расширен материал, относящийся к теории игр и к алгоритмически неразрешимым проблемам. Для второго издания впервые написаны §§ 2, 12 и 13. Остальные параграфы книги подверглись существенной переработке.

Тем, кто пожелает более основательно ознакомиться с вопросами, затронутыми в этой книге, можно рекомендовать следующую литературу:

1. А. А. Марков, Теория алгорифмов, Труды матем. ин-та им. Стеклова, т. XLII, Изд-во Академии наук СССР, Москва, 1954 г.

2. Р. Петер, Рекурсивные функции, Москва, 1954 г.

3. А. И. Китов, Электронные вычислительные машины, Изд-во Советское радио, Москва, 1956 г.

4. А. И. Китов и Н. А. Криницкии, Электронные цифровые машины и программирование, Физматгиз, Москва, 1959 г.

5. С. Клини, Введение в метаматематику, ИЛ, Москва, 1956 г.