Рэймонд Смаллиан - Принцесса или тигр?

в) Рассмотрим вновь машину со свойствами 1 и 2. Возьмем произвольное число h; тогда, согласно пункту «б» нашего решения (если положить b равным h ), существует по крайней мере одно число х, такое, что число М(х, h) будет отличаться по четности от числа х. Значит, число М(х, h) не может иметь ту же самую четность, что и число x для всех х; другими словами, свойство 3 оказывается невыполнимым. Таким образом, свойства 1, 2 и 3, если воспользоваться словцом Амброза Бирса, [11] Амброз Бирс (1842–1914) — американский писатель. На русский язык неоднократно переводились его рассказы. — Прим. перев. «несосуществимы».

Примечание.Невозможность построения машины Уолтона тесно связана с теоремой Тарского (гл. 15). Поэтому для доказательства этой теоремы и для доказательства невозможности существования подобной машины можно использовать одни и те же рассуждения.

Фергюссон (да, по-своему, как и чудаковатый Уолтон) пытался создать нечто такое, что в случае успеха можно было бы считать осуществлением самой страстной мечты Лейбница; ведь Лейбниц серьезно размышлял о возможности создания счетной машины, которая могла бы решить все математические проблемы, а заодно и философские! Однако мечта Лейбница о машине, решающей любые математические задачи (а философские проблемы тем более), оказалась недостижимой. Этот вывод следует из результатов. полученных Гёделем, Россером, Черчем, Клини, Тьюрингом, Постом. К их работам мы сейчас и обратимся.

Существует определенный класс счетных машин. назначение которых состоит в том, чтобы производить, те или иные математические операции над положительными целыми числами. Мы подаем на вход такой машины некое число x и получаем на выходе новое число у. Например, можно легко представить себе машину (не очень, понятно, интересную), которая при подаче на ее вход числа x дает нам на выходе число х + 1. Обычно говорят, что такая машина выполняет операцию прибавления единицы. Можно сделать машину, которая выполняет, скажем, операцию сложения двух чисел. В такой машине мы сначала подаем на вход число х, потом число у, затем нажимаем кнопку и через какое-то время получаем на выходе число х + у. (Для таких машин имеется свое техническое название — их, по-моему, называют суммирующими машинами!)

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

Мы задаем машине две команды (1) напечатать число 2; (2) если напечатано число n , то напечатать число n + 2. (Разрешается задавать вспомогательные правила, которые определяют порядок выполнения команд таким способом, чтобы машина в конечном счете выполнила все, что она может выполнить.) Такая машина, подчиняясь команде (1), рано или поздно напечатает число 2, а напечатав 2 она в конце концов, подчиняясь команде (2), напечатает число 4, затем, напечатав 4, она, опять же руководствуясь командой (2), напечатает число 6, потом числа 8, 10 и т. д. Тем самым наша машина будет генерировать множество четных чисел. (Отметим, что без введения дополнительных команд она никогда не сможет произвести нам числа 1, 3, 5 или любое другое нечетное число.) Чтобы запрограммировать машину на генерирование нечетных чисел, нам следует просто заменить первую команду на команду «напечатать число 1». Иногда объединяют вместе две или несколько машин, с тем чтобы информация на выходе одной машины могла быть использована в другой. Пусть, например, у нас имеются две машины, А и В, программу для которых мы составим следующим образом. Машине А мы зададим две команды: (1) напечатать число 1; (2) если машина В напечатала число n , то напечатать число n + 1. Машине В мы задаем только одну команду: (1) если машина А напечатала число n , то напечатать число n + 1. Какие числа будет генерировать машина А, а какие — машина В? Ответ: машина А будет генерировать множество нечетных чисел, а машина В — множество четных чисел.

Теперь представим себе, что программа для генерирующей машины записывается не на естественном языке, а кодируется в виде некоторого целого числа (представляющего собой цепочку цифр); кодирование можно осуществить так, чтобы каждое положительное целое число представляло собой номер определенной программы. Пусть М n — это машина, программа которой имеет кодовый номер n. Расположим теперь все генерирующие машины в виде бесконечной последовательности М 1, М 2…, М n … ( М 1— это машина с номером программы 1, М 2— машина с номером программы 2 и т. д.)

Для любого множества чисел А (естественно, имеется в виду множество положительных целых чисел) и для любой машины M мы будем говорить, что машина M генерирует множество А, или, иначе, машина M перечисляет множество А, если каждое число, входящее в множество А, в конце концов будет напечатано машиной M, и в то же время ни одно число, не входящее в А, этой машиной напечатано не будет. Множество А мы будем называть эффективно перечислимым (иногда говорят — рекурсивно перечислимым ), если существует хотя бы одна машина М i которая перечисляет множество А. Кроме того, мы будем говорить, что множество А разрешимо (или рекурсивно ), если существуют одна машина М i , которая перечисляет само множество А, и другая машина М j которая перечисляет множество всех чисел, не входящих в А. Таким образом, множество А является разрешимым том и только том случае, если и A, и его дополнение A̅ являются эффективно перечислимыми.

Предположим, что множество А — разрешимо и у нас имеются машина М i , которая генерирует А, и машина М j которая генерирует дополнение A̅ . Тогда оказывается, что существует эффективный способ, позволяющий определять, входит ли некоторое число n в множество А или нет. Допустим, к примеру, нас интересует, входит ли в множество А число 10. Мы приводим в действие обе машины одновременно и ждем. Если число 10 принадлежит множеству А, то рано или поздно это число будет напечатано машиной М i , так что мы сразу узнаем, что число 10 входит в А. Если же число 10 не принадлежит множеству А, то в конце концов это число напечатает машина М j — тем самым мы сразу узнаем, что число 10 не входит в А. Таким образом, в конечном итоге мы обязательно выясним, принадлежит ли число 10 множеству А или нет. (Понятно, что сказать заранее, сколько нам придется ждать, невозможно; нам известно лишь, что через какой-то конечный промежуток времени мы непременно узнаем ответ.)