Принцесса или тигр, стр. 46

— Пока все ясно, — сказал Крейг.

— Кроме того, — продолжал Уолтон, — под словом «число» я понимаю произвольное положительное целое число, поскольку только эти числа я и буду рассматривать в дальнейшем. Как вам, должно быть, известно, обычно говорят, что два натуральных числа имеют одинаковую четность, если они одновременно либо оба четны, либо оба нечетны; если же одно из них четно, а другое нечетно, то их называют числами с различной четностью.

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

Свойство 1. Для любого числа a должно существовать некоторое число b, такое, что при любом х число М(х, b) будет иметь ту же самую четность, что и число М(х*,а).

Свойство 2. Для любого числа b должно существовать некоторое число а, такое, что при любом х число М(х, а) будет иметь другую четность по сравнению с числом М(х, b).

Свойство 3. Должно существовать число h, такое, что при любом х число М(х, h) будет иметь ту же самую четность, что и само х.

— Вот такими свойствами должна обладать моя машина, — заключил Уолтон.

Инспектор Крейг некоторое время молчал, размышляя.

— Ну и в чем же дело? — спросил он наконец.

— Увы! — отвечал Уолтон. — Сначала я построил машину со свойствами 1 и 2, потом — машину со свойствами 1 и 3, наконец, я сконструировал машину со свойствами 2 и 3. Все три машины прекрасно работают — вон там, в портфеле, у меня подробные схемы… Но когда я пытаюсь объединить все три свойства в одной машине, у меня ничего не получается.

— Что же именно у вас не получается? — поинтересовался Крейг.

— Да она вообще не работает! — воскликнул Уолтон с отчаянием. — Когда я ввожу в нее пару чисел (х, у), то вместо того, чтобы выдать мне результат, машина вдруг начинает странно гудеть, как будто в ней происходит нечто вроде короткого замыкания. Как вы думаете, отчего это может быть?

— Да-а, — покачал головой Крейг. — Здесь есть над чем подумать. Правда, сейчас мне надо уйти, меня ждут, но если вы оставите мне свою визитную карточку или просто фамилию и адрес, то я немедленно дам знать, как только во всем этом разберусь.

Через несколько дней инспектор Крейг написал Уолтону письмо. Начиналось оно так:

Дальше Крейг объяснял, почему существование подобной машины логически невозможно. Можете ли вы сообразить, почему?

Полезно разбить решение этой задачи на три этапа:

1) показать, что для любой машины, обладающей свойством 1, при любом числе а должно существовать по крайней мере одно число х, такое, что число М(х, а) будет иметь ту же самую четность, что и само х;

2) показать, что для любой машины, обладающей свойствами 1 и 2, при любом числе b найдется некоторое число х, такое, что число М(х, b) будет иметь иную четность по сравнению с этим х;

3) ни одна машина не может объединить в себе свойства 1, 2 и 3.

Решение

а) Рассмотрим машину, обладающую свойством 1. Возьмем произвольное число а; тогда, согласно свойству 1, найдется число b, такое, что при любом х число М(х, b) будет иметь ту же самую четность, что и число М(х* а). В частности, если положить х равным b, то число M(b, b) будет обладать той же самой четностью, что и число М(b*, а). Однако число М(b, b) — это просто b*, и, значит, число b* должно иметь ту же самую четность, что и число М(b*, а). Таким образом, положив х равным числу b*, мы видим, что число М(х, а) имеет ту же самую четность, что и само число х.

б) Рассмотрим теперь некоторую машину, обладающую свойствами 1 и 2. Возьмем произвольное число b; тогда, согласно свойству 2, обязательно найдется число a, такое, что при любом х число М(х, а) будет иметь другую четность по сравнению с числом М(х, b). Но, согласно свойству 1, существует по крайней мере одно х, при котором число М(х, а) имеет ту же самую четность, что и само х, — мы только что доказали это в пункте а. Такое число х должно иметь другую четность по сравнению с числом М(х, a), поскольку оно одинаково по четности с числом М(х, а), а М(х, а) в свою очередь имеет иную четность по сравнению с числом М(х, b).

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

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

Мечта Лейбница

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

Существует определенный класс счетных машин. назначение которых состоит в том, чтобы производить, те или иные математические операции над положительными целыми числами. Мы подаем на вход такой машины некое число х и получаем на выходе новое число у. Например, можно легко представить себе машину (не очень, понятно, интересную), которая при подаче на ее вход числа х дает нам на выходе число х+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. Какие числа будет генерировать машина А, а какие — машина В? Ответ: машина А будет генерировать множество нечетных чисел, а машина В — множество четных чисел.