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

• Название: Принцесса или тигр
• Автор: Рэймонд Смаллиан
• Жанр: Математика

Задачи по логике

---

— Нашел! Нашел! Еще чуть-чуть и я стану самым великим математиком на свете! Евклид, Архимед, Гаусс — все канут в Лету! А Ньютон, Лобачевский, Бойаи, Риман — разве…

— Спокойно, спокойно, — не повышая голоса, но достаточно твердо прервал его Крейг. — Что же именно вы нашли?

— Еще не совсем нашел, — отвечал незнакомец уже не так возбужденно. — Но вот-вот найду и, когда найду, стану самым великим математиком всех времен и народов! Имена Галуа, Коши, Дирихле, Кантора…

— Ну хватит! — решительно сказал Крейг. — Может быть, вы все же расскажете мне, что именно вы хотите найти?

— Хочу найти? — воскликнул незнакомец с обидой. — Говорю вам, я почти нашел! Я почти придумал универсальную машину, которая сможет решать любые математические задачи! Имея такую машину, я буду знать все! Я смогу…

— А, мечта Лейбница! — сказал Крейг. — Лейбниц ведь тоже мечтал о такой машине. Боюсь только, что мечта эта неосуществима.

— Лейбниц! — презрительно усмехнулся незнакомец. — Лейбниц! Да он просто не знал, с чего начать! А у меня практически уже есть такая машина! Не хватает только нескольких мелочей… Но давайте я вам лучше поподробней расскажу о своих идеях.

— Я хочу построить некую машину М, — начал объяснения незнакомец (как выяснилось, звали его Уолтон), — с вполне определенными свойствами: сначала вы вводите в машину натуральное число х, потом натуральное число у — и тут машина начинает работать и выдает некоторое новое число, которое мы будем обозначать как М(х, у). Итак, М(х, у) — это результат, который мы имеем на выходе машины М в том случае, если на ее входе в качестве первого числа задать число х, а в качестве второго — число у.

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

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

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

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