Иван Долмачев

ГЛАВА IV

В предыдущей главе (см.: "Информатика", № 48/99) я рассказал о двух выдающихся открытиях, сделанных в конце XIX в. немецким математиком Георгом Кантором:

диагональном процессе и доказательстве несчетности множества всех действительных чисел. Понятие "несчетности" можно проиллюстрировать "в программистских терминах" следующим образом.

Представим себе, что имеется "бесконечный массив" х:

х[1], х[2], х[3], х[4],... ,

— т.е. "массив", индексы которого изменяются от единицы до бесконечности. (Конечно, такой массив нельзя реализовать ни на одном компьютере — в данном случае мы имеем дело с математической абстракцией. Эта абстракция ничем не отличается от абстракции "бесконечной последовательности" х₁, х₂, x₃, x₄ ..., с которой часто приходится иметь дело в школьной математике.) Вообразим, что каждая из ячеек массива х способна "запоминать" любое действительное число со всеми его десятичными  знаками после запятой, даже если этик знаков бесконечно много. (Это требование — тоже математическая абстракция: для запоминания чисел с бесконечным числом знаков потребовалось бы бесконечное количество байт.)

Теперь представим себе, что в каждую ячейку (элемент) массива х "записано" какое-нибудь действительное число (с абсолютной точностью, со всеми своими десятичными знаками). Оказывается, что тогда всегда найдется некоторое действительное число, которое отличается от содержимого любой из ячеек х [1], х [2], х [3] \ х[4], ... (Это и есть, по сути, теорема Кантора о несчетности множества всех действительных чисел.) Другими словами, как бы мы ни старались "разместить" все действительные числа по ячейкам массива х, у нас ничего не выйдет: всегда найдется число, для которого в этом массиве "не хватит места" (а на самом деле, как легко понять, найдется даже бесконечно много таких чисел). Это поразительный факт. Ведь никого не удивит, что если бы массив х имел только, скажем, 10 элементов: х[1], х[2], х [3],..., х [10], — то никакими усилиями мы не смогли бы разместить по его ячейкам, например, 15 различных чисел (конечно, мы считаем, что в каждую ячейку массива можно записать лишь одно число). Это совершенно очевидно просто потому, что 15 больше 10 и для пяти чисел из пятнадцати никогда не будет хватать места.

Мы же имеем дело с "бесконечным массивом" х. Казалось бы, в бесконечном массиве можно разместить и любую бесконечную совокупность. Он ведь настолько "большой", что в него "поместится" даже все множество натуральных чисел (бесконечное!): 1, 2, 3, 4, ... Чтобы убедиться в этом, можно "присвоить" натуральные, числа элементам массива х следующим образом: х [1] :=1, х [2] :==2, х [3] :=3 и т.д. (Внимательный читатель, читавший главу III, конечно, заметил, что "размещение" какого-то множества в элементах массива х — это то же самое, что пересчет этого множества.) Но если вместо множества всех натуральных чисел взять множество всех действительных чисел, то оно уже "не поместится" в наш массив х (т.е. оно не допускает никакого пересчета, оно несчетно) — подобно тому, как 15 чисел не помещаются в массив из 10 элементов (см. выше). И, подобно тому, как 15 больше 10, "количество" всех действительных чисел "больше", чем "количество" всех натуральных чисел.

Таким образом, существуют различные уровни бесконечного: одно бесконечное количество в определенном смысле может быть больше, чем другое бесконечное количество. Кантор в своих работах придал понятию сравнения бесконечных количеств (больше, меньше, равно) точный математический смысл, а открытие им различных уровней бесконечного вместе с другими оригинальными идеями привели его к изобретению так называемых трансфинитных чисел и созданию развитой общей теории бесконечных множеств.

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

В оставшейся части этой главы мы рассмотрим знаменитые парадокс Рассела и проблему остановки, в их связи с канторовским диагональным процессом. Здесь мы ограничиваемся только их изложением, чтобы читателю стало окончательно ясно, зачем в предыдущей главе столь много внимания было уделено канторовскому диагональному процессу.

Парадокс Рассела

Бертран Рассел (1872—1970) — выдающийся логик, философ, математик и социолог, лауреат Нобелевской премии по литературе (1950). Не будет большим преувеличением сказать, что наибольшую известность среди самого широкого круга людей ему принесли не его. многочисленные математические и философские работы, а всего лишь одна логическая головоломка — "парадокс деревенского брадобрея".

Я люблю математику за то, что в ней нет ничего человеческого, за то, что с нашей планетой, со всей Вселенной ее, по существу, ничего не связывает. За то, что любовь к ней... безответна.

Многие готовы скорее умереть, чем подумать. Часто, кстати, так и бывает.

Никто никогда не сплетничает о тайных достоинствах других людей.

Зависть — основа демократии.

От страха способен избавиться лишь тот, кто знает свое место; величия может достигнуть лишь тот, кто видит свое ничтожество.

Если какая-то точка зрения широко распространена, это вовсе не значит, что она не абсурдна. Больше того. Учитывая глупость большинства людей, широко распространенная точка зрения будет скорее глупа, чем разумна.

"Правильно жить" означает лицемерие, "правильно думать" — глупость.

Человек доказывает свое превосходство перед животными исключительно способностью к занудству.

Неординарные люди равнодушны к счастью — особенно к чужому.

В наш опасный век есть немало людей, которые влюблены в несчастья и смерть и очень злятся, когда надежды сбываются-

Род людской — это ошибка. Без него Вселенная была бы не в пример прекраснее.

(Из афоризмов Бертрана Рассела [3] )

Рассел открыл свой парадокс, относящийся к области логики и математики, в 1902 г. Оказалось, что в теории множеств Кантора, которая с восторгом была принята большинством математиков, имеются странные противоречия, от которых невозможно, или по крайней мере очень трудно, избавиться. Парадокс Рассела особенно ярко выявил эти противоречия. Впрочем, аналогичный парадокс был независимо открыт выдающимся немецким математиком Эрнстом Цермело (1871— 1953), который не стал его публиковать, а лишь сообщил о нем Гильберту. Парадокс Рассела (точнее, Рассела — Цермело), по словам Гильберта, оказался катастрофой для математиков. Над его разрешением, так же, как и над разрешением других найденных парадоксов канторовской теории множеств, трудились самые выдающиеся математики тех-лет, и, собственно говоря, описание Тьюрингом своей "машины" в 1936 г. в известном смысле находилось в "струе" решений тех логико-математических проблем, которые исследовались в связи с парадоксами теории множеств.

Мы пока не будем говорить о том, в чем состоял парадокс Рассела — Цермело и почему он был воспринят как катастрофа для математики, а опишем его популярную форму, которую придумал сам Рассел в 1919 г. [2].

В некоторой деревне живет брадобрей, который объявил, что он бреет всех жителей деревни, которые не бреются сами, но, разумеется, не бреет тех жителей, которые бреются сами. (Математик выразил бы это правило так:

"Брадобрей бреет тех и только тех жителей деревни, которые не бреются сами".) Однажды брадобрей задумался: должен ли он брить самого себя ? Если он будет брить себя, то, поскольку он бреет только тех, кто не бреется сам, он не должен себя брить. Если же он не будет бриться сам, то тогда он должен себя брить... Он оказался в безвыходном положении — он не мог ни брить себя, ни не брить.

Этот парадокс оказывается тесно связанным с канторовским диагональным процессом. Пусть п — число жителей деревни. Занумеруем каждого жителя деревни числами от 1 до п. Нарисуем квадратную таблицу из п строк и п столбцов. В каждой клетке таблицы поставим крестик или нолик по следующему правилу: если житель номер i бреет жителя номер ;', то в клетке, находящейся в строке номер i и столбце номер ;', поставим крестик, иначе — нолик, Может получиться, скажем, таблица, изображенная на рис. \а (в случае п == 5; согласно этой таблице, например, житель номер 3 бреется сам, но не бреет жителя номер 5).

Рис. 1

Эту таблицу представим в виде двухмерного массива Т, т.е. пусть T[i, j} — это элемент таблицы (крестик или нолик), находящийся в строке номер i и столбце номер ;. Пусть также D — одномерный массив длины п заполненный крестиками и ноликами следующим образом: если наш Брадобрей (будем писать его с прописной буквы) бреет жителя номер i, то D[i] — крестик, иначе— нолик. (Как обычно, D[i] обозначает i-й элемент массива D. Структура массива D показана на  рис. 16.) Правило "Брадобрей бреет тех и только тех жителей деревни, которые не бреются сами", можно выразить так:

 D[i] не равно Т [i, i} для всех индексов i.   (*)

При нашей нумерации жителей деревни Брадобрей тоже должен был получить какой-то номер. Какой? Если его номер, скажем, i, то тогда, согласно правилу построения таблицы Т, массив D должен был бы целиком совпадать со строкой номер i таблицы Т, Другими словами, должно быть:

D[j]== T[i, j] для всех индексов j.

Но это невозможно: если в предыдущем равенстве положить ; равным i, то получится D[i] = Т [i, i] — противоречие с требованием (*). На самом деле мы имеем ровно ту же ситуацию, которая подробно была разобрана в предыдущей главе: из требования (*) следует, что строка D не может совпадать ни с одной из строк таблицы Т, причем мы почти дословно повторили приведенное там доказательство этого факта.

Иногда считают, что "парадокс брадобрея" "снимается" как раз тем, что выявленное противоречие доказывает, что такого брадобрея не может существовать вообще. (В рассуждениях с таблицей Т и массивом D противоречие заключается в следующем. С одной стороны, массив D должен совпадать с одной из строк таблицы Т, поскольку Брадобрей должен иметь определенный номер среди жителей деревни, но, с другой стороны, из требования (*) заключаем, что массив D не совпадает ни с одной из строк таблицы Т.) Сам же Рассел не признавал такого "объяснения" своего парадокса, и мы еще вернемся к этому вопросу. Пока же нас интересовала связь парадокса Рассела с канторовским диагональным процессом. (Напомним, что требование (*) составляет "соль" канторовского диагонального процесса.)

Можно упомянуть еще один логический парадокс — "парадокс голландских мэров", сходный с парадоксом брадобрея (см., например, [1] ). Каждый муниципалитет в Голландии должен иметь мэра, и два разных муниципалитета не могут иметь одного и того же мэра. Иногда оказывается, что мэр не проживает в своем муниципалитете. Допустим, что издан закон, согласно которому некоторая территория S выделяется исключительно для таких мэров, которые не живут в своих муниципалитетах, и предписывающий всем этим мэрам поселиться на этой территории. Допустим, далее, что этих мэров оказалось столько, что территория S сама образует отдельный муниципалитет. Где должен проживать мэр этого Особого Муниципалитета S? (Простое рассуждение показывает, что если мэр Особого Муниципалитета 5 проживает на территории S, то он не должен проживать там, и наоборот, если он не проживает на территории 5, то он как раз и должен жить на этой территории.) То, что этот парадокс аналогичен парадоксу брадобрея, совершенно очевидно. Любознательный читатель в качестве упражнения может подробно разобрать и здесь связь с канторовским диагональным процессом, используя обозначения Т и D. (Подсказка: Т [j, i] — крестик, если мэр муниципалитета номер j живет на территории муниципалитета номер i, а иначе — нолик; D [i] — крестик, если мэр муниципалитета номер i проживает на территории Особого Муниципалитета S, иначе — нолик.)

А вот еще один родственный парадокс — "парадокс библиотекаря конгресса", придуманный математиком Ф.Гонсеттом (1933 г., см. [1]). Библиотекарь конгресса США составляет библиографию всех тех библиографий, которые не перечисляют самих себя. Должен ли он включать в эту библиографию ее саму? (Читатель может и здесь установить связь с канторовским диагональным процессом, определив надлежащим образом массив-таблицу Т и массив-строку D.)

Тьюринговская проблема остановки

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

х:= 1;
Repeat
{ какие-то действия, которые не изменяют значение переменной x. };
Until x>10

Такой фрагмент вполне мог бы возникнуть из-за невнимательности программиста.

"Зацикливание программ" является очень неприятной вещью: при прогоне такой программы часто бывает непонятно, то ли она просто "долго считает", то ли она "зациклилась". В программах, написанных школьниками, такая ситуация возникает достаточно часто.

Зададимся следующим вопросом. Нельзя ли определить программным способом, с помощью самого компьютера, "зациклится" ли данная программа? Может быть, можно написать некоторую универсальную программу (обозначим ее через U), которая принимала бы на вход текст заданной программы, анализировала его и выдавала бы ответ, "зациклится" эта программа или нет. Возможность написания программы U кажется правдоподобной: ведь если мы подозреваем какую-то нашу программу на "зацикленность", мы анализируем ее текст, запускаем трассировку (пошаговую отладку), наблюдая, "что происходит внутри программы". Быть может, этот процесс лучше поручить компьютеру? Ведь, например, программа-компилятор "умеет" анализировать текст заданной программы, "отлавливать" в нем возможные синтаксические ошибки и т.п. Программа U могла бы стать "надстройкой" над компилятором, которая "вылавливала" бы ошибку особого рода — ошибку "бесконечного цикла".  

Уточним формулировку задачи. Каждая программа П в каждом конкретном случае работает со входными данными. (Строго говоря, некоторые программы, например какая-нибудь программа вычисления числа пи с точностью до 100 000 знаков, могут и "ничего не получать на вход" — в этом случае будем считать, что входные данные для такой программы образуют "пустой набор", файл из нуля байт.) Можно считать, что эти входные данные берутся всегда из какого-то файла Д. Действительно, как легко догадаться, все входные данные — символы, вводимые с клавиатуры, файлы и даже движения мышки — можно закодировать в одном общем файле данных. Может случиться, что некоторая программа, получая на вход одни данные, "зацикливается", а получая другие — нет. (Например, если бы во фрагменте программы на Паскале, приведенном выше, вместо присваивания х:= 1 стоял бы вызов процедуры чтения Readin (х), то при вводе "1" программа бы зациклилась в этом месте, а при вводе "12" — нет.)

Работу программы U можно спроектировать следующим образом. Программа U должна получать на вход, во-первых, текст программы П (текстовый файл), а во-вторых, некоторый файл с данными Д. Затем она должна проанализировать эти два файла и выдать точный ответ, "зациклится" ли программа П, если П получила на вход файл Д. Можно всегда считать, что программа U может воспринимать на вход любые файлы: например, если файл П не является синтаксически правильной программой на выбранном языке программирования (скажем, Паскале), то программа U это легко определяет, но все равно считает, что в этом случае П является "программой": например, такой, которая "ничего не делает" и, следовательно, не "зацикливается". Соответственно, если файл Д имеет "неправильный формат" (например, на вход программе П требуется число, а в файле Д имеется что-то другое), то программа П всегда останавливается на этих "неправильных данных". Итак, вот более точное описание нашего проекта:

а) программа U читает два произвольных файла: П иД;

6) если файл П содержит синтаксически правильную программу (для определенности - на Паскале), а файл Д представляет собой подходящие данные для программы П, то программа U проверяет, "зациклится" ли П на данных Д. Если она зациклится, то на экран компьютера будет выдано сообщение "зациклится", иначе — "не зациклится";

в) если файлы П и Д не удовлетворяют условиям б, то на экран выдается сообщение "не зациклится" (и  в этой ситуации для простоты, мы все равно называем П "программой", а Д — "данными", и П в этом случае не "зацикливается" на Д "по определению" ).

Будем считать, что для работы программы U в нашем распоряжении имеется "идеальный" компьютер без обычных ограничений .на объем памяти (т.е. при любом вычислении на этом компьютере можно выделить любой необходимый объем памяти, компьютер способен работать со сколь угодно большими данными). Забудем даже о любых соображениях эффективности — нам абсолютно все равно, как долго будет работать программа U, лишь бы в конце концов она выдала ответ. Таким образом, мы интересуемся только теоретической, принципиальной возможностью написания программы U, пусть даже ее размер в байтах окажетется повышающим число частиц во Вселенной, а время работы — больше времени жизни Вселенной...

Предположим, что нам удалось написать такую программу U. Можно считать, что она тоже написана на Паскале. Теперь мы собираемся написать новую программу, которую обозначим через U1. Но прежде мы введем специальное понятие — стандартный номер файла. Любой файл можно представить как "слово", быть может, очень длинное. Каждая "буква" этого слова берется из некоторого "алфавита". Например, в соответствии с архитектурой "привычных" нам на сегодняшний день компьютеров, можно считать, что алфавит для таких "слов" состоит из 256 символов, а каждая буква в "слове" — это один байт в файле; в качестве "букв" здесь выступают все символы — "настоящие буквы", знаки препинания, пробел, специальные символы и т.д. Можно и по-другому. Каждый байт в файле определяется двумя шестнадцатеричными цифрами (от 0 до F). Тогда наш алфавит состоит из 16 "букв": О, 1, ..., А, В, С, D, Е, F. Любой файл можно себе представить как некоторую последовательность этих символов, т.е. как слово из букв этого алфавита. В любом случае все файлы могут быть расположены в некоторую бесконечную последовательность:

Ф₁, Ф₂, Ф₃, Ф₄ ....                 (**)

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

Можно также написать программу, которая по заданному числу восстанавливает файл, стандартный номер которого равен п (это, впрочем, немного сложнее).

Итак, любой файл попадает в последовательность (**) и имеет в ней свой уникальный номер, который мы называем стандартным номером этого файла. Значит, и у любого файла с программой (П), и у любого файла данных (Д) есть свои стандартный номер.

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

1) получать на вход натуральное число i

2) восстанавливать файл Фi из последовательности (**), т.е. восстанавливать файл со стандартным номером i;

3) запускать программу U, подавая ей на вход в качестве файла П файл Фi., а в качестве файла Д — тот же самый файл Фi. (можно, конечно, просто включить текст программы U в текст U1). Коротко работу программы U1 можно описать так: по заданному числу i она определяет, "зациклится" ли программа, реализованная в файле со стандартным номером i при работе с данными, записанными в файле, который имеет стандартный номер i.

Ясно, что программу U1 всегда можно написать так, чтобы она заканчивалась строками:

If z=0 then

(A)       Writeln("He зациклится")

Else       Writein("зациклится")

(в самом конце работы некоторая переменная z получает значение 0 или 1, и в соответствии с этим значением выдается одно из двух сообщений). Теперь подвергнем программу U1 маленькой переделке. Фрагмент, приведенный выше, заменим на такой:

If z=0 then

(Б)        Repeat
             Until 2=3
      Else
         Writein("зациклится")

Эту программу (назовем ее U2) сохраним в другом файле. Что делает U2? Она тоже, как и U1, получает на вход число i, но отличается от U1 вот чем: если выяснилось, что исследуемая программа со стандартным номером i не "зацикливается" на файле данных со стандартным номером j, то сама U2 "зацикливается", а в противном случае U2 выдает сообщение "зациклится" и после этого завершает работу.

Программа U2 сама, конечно, записана в файле. Этот файл обязательно находится в последовательности (**) и имеет некоторый стандартный номер. Пусть k — этот номер. Здесь начинается самое интересное. Что произойдет, если на вход программе U2 в качестве числа i мы подадим число k? В этом случае, конечно, выполнение программы U2 может либо "зациклиться", либо остановиться. Предположим, что оно остановится. Тогда, как только компьютер дойдет до выполнения фрагмента (Б), переменная z должна получить нулевое значение (вспомним, как была написана программа U2, см. также фрагмент (А) ). После этого, в соответствии с (Б), произойдет "зацикливание". Предположив, что выполнение остановится, мы выяснили, что выполнение зациклится! Это невозможно. Теперь предположим, что выполнение зациклится. Но тогда программа U2, как говорилось выше, должна выдать сообщение "зациклится" и после этого остановиться. Это тоже невозможно.

Эта парадоксальная ситуация нам уже знакома: она удивительно похожа на ситуацию с Брадобреем. Почему мы оказались в ней — программа должна "зациклиться", если она остановится, и должна остановиться, если она "зациклится" ? В чем тут дело? Конечно же, в том, что мы предполагали возможность написания универсальной программы U, которая определяла бы любую программу на возможность "зацикливания". Итак, такой программы U не существует в принципе, или, как говорят математики, проблема остановки алгоритмически неразрешима. (Проблема остановки — это и есть то, чем мы занимались: существует ли программа, которая по заданным программе и данным для нее определяла бы, остановится ли эта программа при получении этих данных?)

Осталось еще отметить связь наших рассуждении с канторовским диагональным процессом. Вспомним про массив-таблицу Т и массив-строку D. Здесь T[i,j] — крестик, если программа, реализованная в файле со стандартным номером i, "зацикливается" на данных, расположенных в файле со стандартным номером j, иначе — нолик. Значения T[i,j] для любых заданных i и j могла бы вычислять, после небольших модификаций, программа U (если бы, конечно, она существовала). Значение D [i] — нолик, если программа, реализованная в файле со стандартным номером i , "зацикливается" на данных, расположенных в файле со стандартным номером i, иначе — крестик. Значения D [i] можно было бы вычислять, используя программу U1. Тогда для Т и D выполняется требование (*) и D не совпадает ни с одной строкой таблицы Т.

Неразрешимость проблемы остановки впервые была доказана Аланом Тьюрингом в его работе, опубликованной в 1936 г. Конечно, тогда не было никаких компьютеров и тем более языков программирования, да и сам Тьюринг в той работе даже не пользовался термином "программа". Но его изложение, по сути, мало чем отличалось от нашего. Мы использовали язык Паскаль и говорили о "привычных" нам компьютерах, однако ясно, что эти подробности (о файлах, о конкретном языке программирования) были совсем не важны: существо наших рассуждении было чисто логическим.

***

На этом ряд подробных "предварительных математических отступлений" все-таки еще не заканчивается. В следующих главах я расскажу о парадоксе Рассела в его "математической форме", мы обсудим связь этого парадокса с древним "парадоксом лжеца" и употреблением в обыденной речи "самореферентных высказываний". После этого читателя ждет экскурс в математическую логику и знакомство с выдающимся открытием Курта Гёделя — теоремой о неполноте формальных исчислений, о которой слышали, наверное, очень многие. Затем уже можно будет рассказать о том, в чем состояла "проблема разрешения" (Entscheidungsproblem) Гилбета, и объяснить, почему она была фундаментальной для математической логики. Лишь после этого я, наконец, вернусь к самому Тьюрингу и расскажу о его выдающейся работе 1936 г. "О вычислимых числах, с приложением к Entscheidungsproblem", положившей начало современной теории вычислительных устройств. (Кроме того, в газете "Информатика" будут опубликованы фрагменты этой знаменитой работы — по всей видимости, впервые на русском языке. Читатель также узнает, как выглядела самая первая программа для машины Тьюринга.)

Библиография

1. С.Клини. Введение в метаматематику. Пер. с англ. М.: ИА, 1957.                                  ^;

2. B.Russell. Introduction to mathematical phylosophy. London, New York, 1919.

3. 500 лет английского афоризма. Сост., перев. А.Ливерганта. М.: Терра, 1998.

Продолжение следует