|
б) Рассмотрим теперь некоторую машину, обладающую свойствами 1 и 2. Возьмем произвольное число b; тогда, согласно свойству 2, обязательно найдетс Стр. 211 число a, такое, что при любом х число М(х, а) будет иметь другую четность по сравнению с числом М(х, b). Но, согласно свойству 1, существует по крайней мере одно х, при котором число М(х, а) имеет ту же самую четность, что и само х, — мы только что доказали это в пункте а. Такое число х должно иметь другую четность по сравнению с числом М(х, a), поскольку оно одинаково по четности с числом М(х, а), а М(х, а) в свою очередь имеет иную четность по сравнению с числом М(х, b). в) Рассмотрим вновь машину со свойствами 1 и 2. Возьмем произвольное число h; тогда, согласно пункту «б» нашего решения (если положить b равным h), существует по крайней мере одно число х, такое, что число М(х, h) будет отличаться по четности от числа х. Значит, число М(х, h) не может иметь ту же самую четность, что и число х для всех х; другими словами, свойство 3 оказывается невыполнимым. Таким образом, свойства 1, 2 и 3, если воспользоваться словцом Амброза Бирса*, «несосуществимы». Примечание. Невозможность построения машины Уолтона тесно связана с теоремой Тарского (гл. 15). Поэтому для доказательства этой теоремы и для доказательства невозможности существования подобной машины можно использовать одни и те же рассуждения. 19 Мечта Лейбница Фергюссон (да, по-своему, как и чудаковатый Уолтон) пытался создать нечто такое, что в случае успеха можно было бы считать осуществлением самой страстной мечты Лейбница; ведь Лейбниц серьезно размышлял о возможности создания счетной машины, которая могла бы решить все математические проблемы, а заодно и философские! Однако мечта Лейбница о машине, решающей любые математические задачи (а философские проблемы тем более), оказалась недостижи- * Амброз Бирс (1842—1914) — американский писатель. На русский язык неоднократно переводились его рассказы.— Прим. Персе. Стр.212 мой. Этот вывод следует из результатов. полученных Гёделем, Россером, Черчем, Клини, Тьюрингом, Постом. К их работам мы сейчас и обратимся. Существует определенный класс счетных машин. назначение которых состоит в том, чтобы производить, те или иные математические операции над положительными целыми числами. Мы подаем на вход такой машины некое число х и получаем на выходе новое число у. Например, можно легко представить себе машину (не очень, понятно, интересную), которая при подаче на ее вход числа х дает нам на выходе число х + 1. Обычно говорят, что такая машина выполняет операцию прибавления единицы. Можно сделать машину, которая выполняет, скажем, операцию сложения двух чисел. В такой машине мы сначала подаем на вход число х, потом число у, затем нажимаем кнопку и через какое-то время получаем на выходе число х + у. (Для таких машин имеется свое техническое название — их, по-моему, называют суммирующими машинами!) — 132 —
|