Принцесса или тигр - Смаллиан Р.М.
Скачать (прямая ссылка):
Теперь для любого числа х мы будем обозначать через х* число вида М(х, х). Так вот, я хочу, чтобы моя машина обладала следующими тремя свойствами. Свойство 1. Для любого числа а должно существовать некоторое число Ь, такое, что при любом х число М(х,Ь) будет иметь ту же самую четность, что и число М(х*, а).
Свойство 2. Для любого числа Ъ должно существовать некоторое число а, такое, что при любом х число
209
М(х, а) будет иметь другую четность по сравнению с числом М(х, Ъ).
Свойство 3. Должно существовать число к, такое, что при любом х число МОс, И) будет иметь ту же самую четность, что и само х.
— Вот такими свойствами должна обладать моя машина,— заключил Уолтон.
Инспектор Крейг некоторое время молчал, размышляя.
— Ну и в чем же дело?—спросил он наконец.
— Увы! — отвечал Уолтон.— Сначала я построил машину со свойствами 1 и 2, потом — машину со свойствами 1 и 3, наконец, я сконструировал машину со свойствами 2 и 3. Все три машины прекрасно работают— вон там, в портфеле, у меня подробные схемы... Но когда я пытаюсь объединить все три свойства в одной машине, у меня ничего не получается.
— Что же именно у вас не получается? — поинтересовался Крейг.
— Да она вообще не работает! — воскликнул Уолтон с отчаянием.— Когда я ввожу в нее пару чисел (х, у), то вместо того, чтобы выдать мне результат, машина вдруг начинает странно гудеть, как будто в ней происходит нечто вроде короткого замыкания. Как вы думаете, отчего это может быть?
— Да-а,— покачал головой Крейг.— Здесь есть над чем подумать. Правда, сейчас мне надо уйти, меня ждут, но если вы оставите мне свою визитную карточку или просто фамилию и адрес, то я немедленно дам знать, как только во всем этом разберусь.
Через несколько дней инспектор Крейг написал Уолтону письмо. Начиналось оно так:
Дорогой мистер Уолтон!
Благодарю Вас за то, что вы посетили меня и рассказали о машине, которую пытались построить. Честно говоря, я не совсем понимаю, каким образом ваша машина, даже если бы вам действительно удалось ее создать, могла бы решать любые математические задачи,—хотя вы, несомненно, разбираетесь в этом лучше меня. Однако должен вам
сказать, что ваш замысел напоминает мне попытку создания вечного двигателя—он также неосуществим! Фактически же дело обстоит гораздо хуже, чем с вечным двигателем. Ведь последний, несмотря на то что он невозможен в нашем физическом мире, все же не является логически невозможным. Машина же, которую хотите создать вы, невозможна не только физически, но и логически, поскольку те три свойства, о которых вы упоминали, содержат в себе определенное логическое противоречие.
Дальше Крейг объяснял, почему существование подобной машины логически невозможно. Можете ли вы сообразить, почему?
Полезно разбить решение этой задачи на три этапа:
1) показать, что для любой машины, обладающей свойством 1, при любом числе а должно существовать по крайней мере одно число х, такое, что число М(х, а) будет иметь ту же самую четность, что и само х;
2) показать, что для любой машины, обладающей свойствами 1 и 2, при любом числе Ь найдется некоторое число х, такое, что число М(х, Ъ) будет иметь иную четность по сравнению с этим х;
3) ни одна машина не может объединить в себе свойства 1, 2 и 3.
Решение
а) Рассмотрим машину, обладающую свойством 1. Возьмем произвольное число а; тогда, согласно свойству 1, найдется число Ь, такое, что при любом х число М(х, Ь) будет иметь ту же самую четность, что и число
а). В частности, если положить х равным Ь, то число Мф, Ъ) будет обладать т.ой же самой четностью, что и число Мф*, а). Однако число Мф, Ь)—это просто Ь*, и, значит, число Ь* должно иметь ту же самую четность, что и число Мф#, а). Таким образом, положив х равным числу Ь#, мы видим, что число М(х, а) имеет ту же самую четность, что и само число х.
б) Рассмотрим теперь некоторую машину, обладающую свойствами 1 и 2. Возьмем произвольное число Ь; тогда, согласно свойству 2, обязательно найдется
211
число а, такое, что при любом х число М(х, а) будет иметь другую четность по сравнению с числом М(х, Ъ). Но, согласно свойству 1, существует по крайней мере одно х, при котором число М(х, а) имеет ту же самую четность, что и само х,—мы только что доказали это в пункте а. Такое число х должно иметь другую четность по сравнению с числом М(х, о), поскольку оно одинаково по четности с числом М(х, а), а М(х, а) в свою очередь имеет иную четность по сравнению с числом М(х, Ь).
в) Рассмотрим вновь машину со свойствами 1 и 2. Возьмем произвольное число к; тогда, согласно пункту «б» нашего решения (если положить Ь равным И), существует по крайней мере одно число х, такое, что число М(х, к) будет отличаться по четности от числа х. Значит, число М(х, к) не может иметь ту же самую четность, что и число х для всех х; другими словами, свойство 3 оказывается невыполнимым. Таким образом, свойства 1, 2 и 3, если воспользоваться словцом Амброза Бирса*, «несосуществимы».
Пр имечание. Невозможность построения машины Уолтона тесно связана с теоремой Тарского (гл. 15). Поэтому для доказательства этой теоремы и для доказательства невозможности существования подобной машины можно использовать одни и те же рассуждения.
