Mybrary.ru

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

Тут можно читать бесплатно Рэймонд Смаллиан - Принцесса или тигр. Жанр: Математика издательство неизвестно, год 2004. Так же Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте mybrary.ru (mybrary) или прочесть краткое содержание, предисловие (аннотацию), описание и ознакомиться с отзывами (комментариями) о произведении.
Название:
Принцесса или тигр
Издательство:
неизвестно
ISBN:
нет данных
Год:
неизвестен
Дата добавления:
13 февраль 2019
Количество просмотров:
127
Читать онлайн
Рэймонд Смаллиан - Принцесса или тигр

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

Рэймонд Смаллиан - Принцесса или тигр - описание и краткое содержание, автор Рэймонд Смаллиан, читайте бесплатно онлайн на сайте электронной библиотеки Mybrary.Ru
Задачи по логике

Принцесса или тигр читать онлайн бесплатно

Принцесса или тигр - читать книгу онлайн бесплатно, автор Рэймонд Смаллиан
Назад 1 ... 39 40 41 42 43 44 Вперед

Итак, главный вопрос, стоящий перед нами, можно сформулировать следующим образом. Пусть V — множество чисел, которые может напечатать универсальная машина U (это множество иногда называют универсальным множеством). Разрешимо множество V или нет? Если оно разрешимо, то мечта Лейбница осуществима; если же нет, то его стремления никогда не смогут быть реализованы. Поскольку V эффективно перечислимо (ведь оно генерируется машиной U), то вопрос сводится к тому, существует ли некая машина Ма, которая сможет напечатать дополнение V, а именно множество V'. Иначе говоря, существует ли такая машина Ма, которая печатает те и только те числа, которые машина U не печатает? На этот вопрос можно дать исчерпывающий ответ лишь на основании утверждений 1 и 2, о которых мы упоминали выше.

Теорема L. Множество V' не является эффективно перечислимым: для любой заданной машины Ма либо существует какое-то число, принадлежащее множеству V, которое машина Ма не может напечатать, либо машина Ма напечатает по крайней мере одно число, которое принадлежит не множеству V', а множеству V.

Сумеет ли читатель доказать теорему L?

Рассмотрим также следующий частный случай. Пусть у нас имеется утверждение о том, что машина М5 перечислила множество V'. Чтобы опровергнуть это утверждение, достаточно отыскать некоторое число n, показав при этом, что либо оно принадлежит множеству V', но не может быть напечатано машиной М5, либо оно не принадлежит множеству V, но машина М5 может его напечатать. Сумеете ли вы найти такое число n?

Я приведу решение этой задачи сразу, а не в конце главы, — по существу, это решение просто повторяет доказательство Гёделя.

Итак, возьмем произвольное число а. Согласно утверждению 2, машина Ма напечатает число х*х, если и только если машина М2а напечатает число х. Но, согласно утверждению 1, машина М2а напечатает число х, если и только если универсальная машина U напечатает число 2а*х, или, что то же самое, если число 2а*х принадлежит множеству V. Следовательно, машина Ма напечатает число х*х, если и только если число 2а*х входит в V. В частности (положив х равным 2а), машина Ма напечатает число 2а*2а, если и только если число 2а*2а принадлежит множеству V. Итак, либо (1): машина Ма напечатает число 2а*2а, и число 2а*2а принадлежит множеству V; либо (2): машина Ма не напечатает число 2а*2а, и число 2а*2а принадлежит множеству V.

Если выполнено условие (1), то машина Ма напечатает число 2а*2а, которое входит не в V, а в V; это означает, что машина Ма не генерирует множество V, потому что она может напечатать по крайней мере одно число 2а*2а, которое не входит в множество V. Если же выполняется (2), то мы опять получаем, что машина Ма не генерирует множество V поскольку число 2а*2а принадлежит множеству V, а машина Ма это число напечатать не может. Итак, в обоих случаях машина Ма не генерирует множество V. В силу произвольности выбора а это означает, что никакая машина не может перечислить множество V, и, следовательно, это множество не является эффективно перечислимым.

Конечно, в частном случае а = 5 число n окажется равным 10*10.

Но все же какое это имеет отношение к мечтам Лейбница? Строго говоря, мы не можем ни доказать, ни опровергнуть возможность осуществления лейбницевых надежд, поскольку они никогда точно не формулировались. Ведь во времена Лейбница не существовало строгого определения понятий «вычислительная машина» или «генерирующая машина»; соответствующие точные определения были получены лишь в нашем веке. Подобных определений имеется много (их вводили Гёдель, Эрбран, Клини, Черч, Тьюринг, Пост, Смаллиан, Марков и многие другие), однако было проверено, что все они эквивалентны между собой. И если под словом «разрешимо» понимать разрешимость в соответствии с любым из этих эквивалентных определений, то мечта Лейбница оказывается неосуществимой по той простой причине, что сами машины можно перенумеровать таким образом, что утверждения 1 и 2 обязательно будут выполняться. Тогда по теореме L множество V, генерируемое универсальной машиной, оказывается неразрешимым — оно будет лишь полу разрешимо. Следовательно, не существует никакой «чисто механической» процедуры, с помощью которой можно было бы узнать, какие утверждения доказуемы в той или иной системе аксиом, а какие нет. Таким образом, любая попытка изобрести некий хитроумный «механизм» для решения всех математических задач обречена на провал.

Это означает, что, выражаясь пророческими словами известного логика Эмиля Поста (1944), математическое мышление является и всегда будет оставаться по сути своей сугубо творческим процессом. Или, как остроумно заметил математик Пол Розенблум, — человеку никогда не избавиться от необходимости пользоваться своим умом, сколько бы ума он не приложил к этому.

Примечания

1

Принцип работы (лат.).

2

Инспектор Крейг—герой моей предыдущей книги логических головоломок «Как же называется эта книга?» (М.: Мир, 1981).

3

Многие задачи этого типа представлены в моей книге "Тhе Сhess Муsteries оf Shеrlоск Ноlmеs" («Шахматные тайны Шерлока Холмса»).

4

От лат. verbalis—словесный. — Прим. ред.

5

Что соответствует случаю, когда одно или два числа из тройки А, В, С мы полагаем равными единице.

6

То есть построение куба с объемом, вдвое большим, чем объем данного куба. — Прим. перев.

7

Некоторые из них оказались весьма интересными, и о них я надеюсь рассказать в своей следующей книге.

8

«Uber formal unentscheidbare Satze der «Principia Mathematica» und verwandter Systeme'I» («О формально неразрешимых предложениях «Принципов математики» и других родственных систем»), Моnatshefte fur Mathematik und Physik, 38, 173–198.

9

Выборочный перевод автора.

10

Смальян Р. Теория формальных систем. Пер. с англ. — М.: Наука, 1981.

11

Амброз Бирс (1842–1914) — американский писатель. На русский язык неоднократно переводились его рассказы. — Прим. Перев.

Назад 1 ... 39 40 41 42 43 44 Вперед

Рэймонд Смаллиан читать все книги автора по порядку

Рэймонд Смаллиан - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки Mybrary.Ru.


Принцесса или тигр отзывы

Отзывы читателей о книге Принцесса или тигр, автор: Рэймонд Смаллиан. Читайте комментарии и мнения людей о произведении.

Прокомментировать
Подтвердите что вы не робот:*
Подтвердите что вы не робот:*
Все материалы на сайте размещаются его пользователями.
Администратор сайта не несёт ответственности за действия пользователей сайта..
Вы можете направить вашу жалобу на почту my.brary@yandex.ru или заполнить форму обратной связи.
×
×