Занимательная задачка по мотивам теоремы Гёделя о неполноте

МЕНЮ


Главная страница
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Альберт Эйнштейн награждает Гёделя (второй справа) наградой, названной в честь него самого

В 1931 году австрийский логик, математик и философ математики Курт Гёдель опубликовал свою теорему о неполноте. Эта работа считается одним из величайших интеллектуальных достижений современности. В теореме утверждается, что в любой разумной математической системе всегда будут существовать истинные утверждения, которые невозможно доказать. Это утверждение шокировало математическую общественность, в которой до того преобладал неистребимый оптимизм, касающийся мощи и всеобъемлющей природы математики. Предполагалось, что математика «полна» — то есть, любое утверждение можно доказать или опровергнуть. 25-летний Гёдель показал, что это не так, составив корректное утверждение, доказать которое невозможно. Таким образом он продемонстрировал ограничения математики.
Теорема о неполноте преобразовала исследования основ математики и станет важным фактором развития информатики, поскольку из неё следует, что у возможностей всех формализованных систем, в том числе и языков программирования, есть свои ограничения.
Эта же теорема лежит и в основе сегодняшней загадки.

Гёдель доказал свою теорему через рекурсию – в формальной математической системе утверждение «Это предложение недоказуемо» будет истинным и формально недоказуемым.

Технические детали теоремы тяжело описать простыми словами. Но американский логик Рэймонд Смальян придумал отличный способ передать дух неполноты через логические загадки о людях, говорящих правду или лгущих. Сегодняшняя загадка вдохновлена его трудами.

Два племени острова Если

В океане Дедукции находится логический остров Если. Рождённые здесь люди принадлежат к одному из двух племён – алетейцам или псевдианцам. Единственный способ отличить их друг от друга – поговорить с ними. Алетейцы всегда говорят правду. Псевдианцы всегда лгут.

В центре острова глава алетейцев хранит Дневник идентичности – в этой книге перечислены имена всех рождённых на острове и их принадлежность к тому или иному племени. Ошибок в Дневнике нет, и его может посмотреть кто угодно.

Однажды на остров Если прибыл бесстрашный искатель приключений. Он встречался с обитателями острова и делил их на алетейцев и псевдианцев путём ловкой постановки вопросов.

После нескольких успешных встреч он познакомился с человеком по имени Курт. Исследователь ещё не знал его принадлежности, но прежде чем он успел задать вопрос, Курт опередил его утверждением: «У вас никогда не будет неопровержимых доказательств того, что я алетеец».

1. Принадлежит ли Курт к алетейцам, к псевдианцам, или ни к одному из племён?

2. Как эта задача связана с теоремой о неполноте?


Источник: habr.com

Комментарии: