Ясно, что указанная комбинация имеет вид RVLVQRVLVQ.
Конечно, задачу о сейфе из Монте-Карло можно решить и не преобразовывая ее в задачу для числовой машины, однако я привел здесь это решение по двум причинам. Во-первых, именно так решал во времени эту задачу сам Крейг, а во-вторых, я подумал, что читателю будет интересно увидеть, как две математические задачи могут иметь разное содержание, но одну и ту же абстрактную форму.
Для того чтобы непосредственно убедиться в том, что комбинация RVLVQRVLVQ является родственной по отношению к самой себе (а значит, и открывает замок), будем рассуждать следующим образом. Комбинация QRVLVQ родственна по отношению к комбинации RVLV (согласно свойству Q), поэтому комбинация VQRVLVQ будет родственной по отношению к обращению комбинации RVLV (согласно свойству V), то есть к комбинации VLVR. Значит, комбинация LVQRVLVQ родственна по отношению к комбинации QVLVR (согласно свойству L), и, следовательно, комбинация VLVQRVLVQ оказывается родственной по отношению к обращению комбинации QVLVR, то есть комбинации RVLVQ. Тогда (согласно свойству R) комбинация RVLVQRVLVQ будет родственной по отношению к повторению комбинации RVLVQ, то есть к комбинации RVLVQRVLVQ. Итак, комбинация RVLVQRVLVQ действительно является родственной самой себе.
Часть четвертая. Разрешима или неразрешима наша задача?
Логическая машина Фергюссона
Через несколько месяцев после того, как была с блеском разрешена загадка банковского сейфа в Монте-Карло, Крейг и Мак-Каллох наконец-то навестили Фергюссона — их очень заинтересовала его логическая машина. Разговор скоро зашел о сущности доказуемости.
— Я расскажу вам интересную и весьма поучительную историю, — сказал Фергюссон. — На экзамене по геометрии одного студента попросили доказать теорему Пифагора. Он сдал свою работу преподавателю, но тот возвратил ее с пометкой: «Это не доказательство!» Молодой человек пошел к преподавателю и сказал: «Сэр, как вы можете утверждать, будто то, что я вам сдал, — не доказательство? За весь курс лекций вы ни разу не дали нам определения доказательства. Вы давали нам строгие определения таких геометрических понятий, как треугольник, квадрат, окружность, параллельность, перпендикулярность и т. д., однако никогда не привели нам точного определения того, что же вы называете доказательством. Как же теперь вы можете так уверенно заявлять, будто мое доказательство — вовсе не доказательство? Как вы можете доказать, что оно не является доказательством?»
— Блестяще! — воскликнул Крейг, захлопав в ладоши. — Этот юноша далеко пойдет. А что же ответил преподаватель?
— К сожалению, — усмехнулся Фергюссон, — преподаватель оказался сухим педантом без чувства юмора и воображения. Он снизил студенту оценку за непочтительность.
— Очень жаль, — с досадой сказал Крейг. — Окажись я на месте преподавателя, непременно поставил бы этому студенту высший балл.
— Разумеется, — согласился Фергюссон, — я бы поступил точно так же. Но вы же прекрасно знаете, как часто преподаватели, лишенные творческого начала, побаиваются способных студентов.
— Должен признаться, — сказал Мак-Каллох, — что на месте этого преподавателя я бы тоже не смог ответить на вопрос студента. Разумеется, я похвалил мы его за толково поставленный вопрос, но ответить на него я бы все-таки не смог. В самом деле, что такое доказательство? Когда я сталкиваюсь с правильным доказательством, я почему-то всегда понимаю, что оно правильно; когда мне попадаются слабые аргументы, я обычно могу их указать. Но если бы меня попросили дать строгое определение доказательства, я тоже оказался бы в весьма затруднительном положении.
— Точно так же, как и почти все работающие математики, — поддержал Мак-Каллоха Фергюссон. — В девяносто девяти процентах случаев они вполне могут распознать правильность доказательства или указать на слабые места в неправильном доказательстве, однако не и состоянии привести точное определение доказательства. Нас же, логиков, интересует прежде всего анализ самого понятия «доказательство» — ведь мы хотим определить его так же строго, как и любое другое математическое понятие.
— Но раз большинство математиков все же понимают, что такое доказательство, хотя и не могут дать его четкого определения, то так ли уж важно искать его? — заметил Крейг.
— Важно, и по нескольким причинам, — ответил Фергюссон. — Но даже не будь этих причин, я все равно котел бы знать это определение ради самого определения. В истории математики часто случалось, что какие-то основные понятия, например понятие непрерывности, интуитивно понимались и осваивались еще задолго до того, как для них было введено строгое определение. Однако, получив четкое определение, данное понятие как бы переходит в новую категорию. Становится возможным установить связанные с ним факты, которые было бы очень трудно или вовсе невозможно открыть, не зная совершенно четко объема этого понятия. В этом смысле не является исключением и понятие «доказательство». Так, иногда случается, что в доказательстве используется какой-нибудь новый принцип — например аксиома выбора — и при этом часто возникает сомнение, является ли применение этого принципа законным. Так вот, строгое определение понятия «доказательство» позволяет точно указать, какие математические принципы можно использовать, а какие нельзя.
С другой стороны, особенно важно иметь точное определение доказательства тогда, когда нужно увидить, что данное математическое утверждение недоказуемо в той или иной системе аксиом. Данная ситуация очень похожа на положение дел с построением при помощи циркуля и линейки в евклидовой геометрии: там, для того чтобы показать, что некое построение (например, трисекция угла, квадратура круга или удвоение куба) невозможно, требуется обычно более критическое определение понятия «построение», чем для того, чтобы показать, например, что то или иное геометрическое построение с помощью циркуля и линейки действительно возможно. То же самое происходит и с доказуемостью: чтобы продемонстрировать, что данное утверждение недоказуемо в некоторой исходной системе аксиом, требуется гораздо более строгое и критическое определение самого понятия «доказательство», чем для получения соответствующего положительного результата, а именно что данное утверждение в самом деле является доказуемым при принятии той или иной аксиомы.
Загадка Гёделя
— Итак, — продолжал Фергюссон, — если задана некоторая система аксиом, то доказательство в данной системе представляет собой конечную последовательность высказываний, построенную по очень строгим правилам. При этом оказывается совсем несложно чисто механическим путем решить, является ли данная последовательность высказываний доказательством в этой системе или нет. Собственно говоря, совсем несложно даже придумать машину, которая может это делать. Гораздо труднее оказывается создать такую машину, которая могла бы решать, какие высказывания в данной системе аксиом доказуемы, а какие нет.
— Ответ, я полагаю, зависит от выбора исходной системы аксиом…
— Сейчас меня интересуют вопросы механического доказательства теорем, то есть вопросы создания таких машин, которые могли бы доказывать различные математические истины.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
Конечно, задачу о сейфе из Монте-Карло можно решить и не преобразовывая ее в задачу для числовой машины, однако я привел здесь это решение по двум причинам. Во-первых, именно так решал во времени эту задачу сам Крейг, а во-вторых, я подумал, что читателю будет интересно увидеть, как две математические задачи могут иметь разное содержание, но одну и ту же абстрактную форму.
Для того чтобы непосредственно убедиться в том, что комбинация RVLVQRVLVQ является родственной по отношению к самой себе (а значит, и открывает замок), будем рассуждать следующим образом. Комбинация QRVLVQ родственна по отношению к комбинации RVLV (согласно свойству Q), поэтому комбинация VQRVLVQ будет родственной по отношению к обращению комбинации RVLV (согласно свойству V), то есть к комбинации VLVR. Значит, комбинация LVQRVLVQ родственна по отношению к комбинации QVLVR (согласно свойству L), и, следовательно, комбинация VLVQRVLVQ оказывается родственной по отношению к обращению комбинации QVLVR, то есть комбинации RVLVQ. Тогда (согласно свойству R) комбинация RVLVQRVLVQ будет родственной по отношению к повторению комбинации RVLVQ, то есть к комбинации RVLVQRVLVQ. Итак, комбинация RVLVQRVLVQ действительно является родственной самой себе.
Часть четвертая. Разрешима или неразрешима наша задача?
Логическая машина Фергюссона
Через несколько месяцев после того, как была с блеском разрешена загадка банковского сейфа в Монте-Карло, Крейг и Мак-Каллох наконец-то навестили Фергюссона — их очень заинтересовала его логическая машина. Разговор скоро зашел о сущности доказуемости.
— Я расскажу вам интересную и весьма поучительную историю, — сказал Фергюссон. — На экзамене по геометрии одного студента попросили доказать теорему Пифагора. Он сдал свою работу преподавателю, но тот возвратил ее с пометкой: «Это не доказательство!» Молодой человек пошел к преподавателю и сказал: «Сэр, как вы можете утверждать, будто то, что я вам сдал, — не доказательство? За весь курс лекций вы ни разу не дали нам определения доказательства. Вы давали нам строгие определения таких геометрических понятий, как треугольник, квадрат, окружность, параллельность, перпендикулярность и т. д., однако никогда не привели нам точного определения того, что же вы называете доказательством. Как же теперь вы можете так уверенно заявлять, будто мое доказательство — вовсе не доказательство? Как вы можете доказать, что оно не является доказательством?»
— Блестяще! — воскликнул Крейг, захлопав в ладоши. — Этот юноша далеко пойдет. А что же ответил преподаватель?
— К сожалению, — усмехнулся Фергюссон, — преподаватель оказался сухим педантом без чувства юмора и воображения. Он снизил студенту оценку за непочтительность.
— Очень жаль, — с досадой сказал Крейг. — Окажись я на месте преподавателя, непременно поставил бы этому студенту высший балл.
— Разумеется, — согласился Фергюссон, — я бы поступил точно так же. Но вы же прекрасно знаете, как часто преподаватели, лишенные творческого начала, побаиваются способных студентов.
— Должен признаться, — сказал Мак-Каллох, — что на месте этого преподавателя я бы тоже не смог ответить на вопрос студента. Разумеется, я похвалил мы его за толково поставленный вопрос, но ответить на него я бы все-таки не смог. В самом деле, что такое доказательство? Когда я сталкиваюсь с правильным доказательством, я почему-то всегда понимаю, что оно правильно; когда мне попадаются слабые аргументы, я обычно могу их указать. Но если бы меня попросили дать строгое определение доказательства, я тоже оказался бы в весьма затруднительном положении.
— Точно так же, как и почти все работающие математики, — поддержал Мак-Каллоха Фергюссон. — В девяносто девяти процентах случаев они вполне могут распознать правильность доказательства или указать на слабые места в неправильном доказательстве, однако не и состоянии привести точное определение доказательства. Нас же, логиков, интересует прежде всего анализ самого понятия «доказательство» — ведь мы хотим определить его так же строго, как и любое другое математическое понятие.
— Но раз большинство математиков все же понимают, что такое доказательство, хотя и не могут дать его четкого определения, то так ли уж важно искать его? — заметил Крейг.
— Важно, и по нескольким причинам, — ответил Фергюссон. — Но даже не будь этих причин, я все равно котел бы знать это определение ради самого определения. В истории математики часто случалось, что какие-то основные понятия, например понятие непрерывности, интуитивно понимались и осваивались еще задолго до того, как для них было введено строгое определение. Однако, получив четкое определение, данное понятие как бы переходит в новую категорию. Становится возможным установить связанные с ним факты, которые было бы очень трудно или вовсе невозможно открыть, не зная совершенно четко объема этого понятия. В этом смысле не является исключением и понятие «доказательство». Так, иногда случается, что в доказательстве используется какой-нибудь новый принцип — например аксиома выбора — и при этом часто возникает сомнение, является ли применение этого принципа законным. Так вот, строгое определение понятия «доказательство» позволяет точно указать, какие математические принципы можно использовать, а какие нельзя.
С другой стороны, особенно важно иметь точное определение доказательства тогда, когда нужно увидить, что данное математическое утверждение недоказуемо в той или иной системе аксиом. Данная ситуация очень похожа на положение дел с построением при помощи циркуля и линейки в евклидовой геометрии: там, для того чтобы показать, что некое построение (например, трисекция угла, квадратура круга или удвоение куба) невозможно, требуется обычно более критическое определение понятия «построение», чем для того, чтобы показать, например, что то или иное геометрическое построение с помощью циркуля и линейки действительно возможно. То же самое происходит и с доказуемостью: чтобы продемонстрировать, что данное утверждение недоказуемо в некоторой исходной системе аксиом, требуется гораздо более строгое и критическое определение самого понятия «доказательство», чем для получения соответствующего положительного результата, а именно что данное утверждение в самом деле является доказуемым при принятии той или иной аксиомы.
Загадка Гёделя
— Итак, — продолжал Фергюссон, — если задана некоторая система аксиом, то доказательство в данной системе представляет собой конечную последовательность высказываний, построенную по очень строгим правилам. При этом оказывается совсем несложно чисто механическим путем решить, является ли данная последовательность высказываний доказательством в этой системе или нет. Собственно говоря, совсем несложно даже придумать машину, которая может это делать. Гораздо труднее оказывается создать такую машину, которая могла бы решать, какие высказывания в данной системе аксиом доказуемы, а какие нет.
— Ответ, я полагаю, зависит от выбора исходной системы аксиом…
— Сейчас меня интересуют вопросы механического доказательства теорем, то есть вопросы создания таких машин, которые могли бы доказывать различные математические истины.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52