Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
19
Мечта Лейбница
Фергюссон (да, по-своему, как и чудаковатый Уолтон) пытался создать нечто такое, что в случае успеха можно было бы считать осуществлением самой страстной мечты Лейбница; ведь Лейбниц серьезно размышлял о возможности создания счетной машины, которая могла бы решить все математические проблемы, а заодно и философские! Однако мечта Лейбница о машине, решающей любые математические задачи (а философские проблемы тем более), оказалась недостижи-
* Амброз Бирс (1842—1914)—американский писатель. На русский язык неоднократно переводились его рассказы.— Прим. перев.
212
мой. Этот вывод следует из результатов, полученных Гёделем, Россером, Черчем, Клини, Тьюрингом и Постом. К их работам мы сейчас и обратимся.
Существует определенный класс счетных машин, назначение которых состоит в том, чтобы производить те или иные математические операции над положительными целыми числами. Мы подаем на вход такой машины некое число х и получаем на выходе новое число у. Например, можно легко представить себе машину (не очень, понятно, интересную), которая при подаче на ее вход числа х дает нам на выходе число ?х + 1. Обычно говорят, что такая машина выполняет операцию прибавления единицы. Можно сделать машину, которая выполняет, скажем, операцию сложения двух чисел. В такой машине мы сначала подаем на вход число х, потом число у, затем нажимаем кнопку и через какое-то время получаем на выходе число х + у. (Для таких машин имеется свое техническое название—их, по-моему, называют суммирующими машинами!)
Существует и другой тип машин, которые можно назвать генерирующими, или перечисляющими, машинами Такие машины будут играть более важную роль в наших последующих рассуждениях (где мы следуем теориям Поста). Эти машины не имеют входов; они запрограммированы на генерирование множества положительных целых чисел. Например, одна машина может генерировать у нас множество четных чисел, другая — генерировать множество нечетных чисел, третья — множество простых чисел, и т. д. При этом типичная машинная программа для генерирования четных чисел может выглядеть так.
Мы задаем машине две команды (1) напечатать число 2; (2) если напечатано число п, то напечатать число п+2. (Разрешается задавать вспомогательные правила, которые определяют порядок выполнения команд таким способом, чтобы машина в конечном счете выполнила все, что она может выполнить.) Такая машина, подчиняясь команде (1), рано или поздно напечатает число 2, а напечатав 2 она в конце концов, подчиняясь команде (2), напечатает число 4, затем, напечатав 4, она, опять же руководствуясь командой
(2), напечатает число 6, потом числа 8, 10 и т. д. Тем
213
самым наша машина будет генерировать множество четных чисел. (Отметим, что без введения дополнительных команд она никогда не сможет произвести нам числа 1, 3, 5 или любое другое нечетное число.) Чтобы запрограммировать машину на генерирование нечетных чисел, нам следует просто заменить первую команду на команду «напечатать число 1». Иногда объединяют вместе две или несколько машин, с тем чтобы информация на выходе одной машины могла быть использована в другой. Пусть, например, у нас имеются две машины, А и В, программу для которых мы составим следующим образом. Машине А мы зададим две команды: (1) напечатать число 1; (2) если машина В напечатала число п, то напечатать число п + 1. Машине В мы задаем только одну команду: (1) если машина А напечатала число п, то напечатать число п + 1. Какие числа будет генерировать машина А, а какие — машина В? Ответ: машина А будет генерировать множество нечетных чисел, а машина В — множество четных чисел.
Теперь представим себе, что программа для генерирующей машины записывается не на естественном языке, а кодируется в виде некоторого целого числа (представляющего собой цепочку цифр); кодирование можно осуществить так, чтобы каждое положительное целое число представляло собой номер определенной программы. Пусть Мп—это машина, программа которой имеет кодовый номер п. Расположим теперь все генерирующие машины в виде бесконечной последовательности Мь М2, ... , М„, ... (М1 — это машина с номером программы 1, М2—машина с номером программы 2 и т. д.)
Для любого множества чисел А (естественно, имеется в виду множество положительных целых чисел) и для любой машины М мы будем говорить, что машина М генерирует множество А, или, иначе, машина М перечисляет множество А, если каждое число, входящее в множество А, в конце концов будет напечатано машиной М, и в то же время ни одно число, не входящее в А, этой машиной напечатано не будет. Множество А мы будем называть эффективно перечислимым (иногда говорят—рекурсивно перечислимым), если существует хотя бы одна машина М„ которая
перечисляет множество А. Кроме того, мы будем говорить, что множество А разрешимо (или рекурсивно), если существуют одна машина М,-, которая перечисляет само множество А, и другая машина М\, которая перечисляет множество всех чисел, не входящих в А. Таким образом, множество А является разрешимым в том и только том случае, если и А, и его дополнение А являются эффективно перечислимыми.
