Неразрешимые задачи – теоретически и практически

[Старый чукотский солдат]

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

Доказано также, что есть задачи сколь угодно трудные. Предположим, что это задачи вычислительные, а трудность измеряется временем вычисления. Или каким-то другим ресурсом, например, объёмом потребной памяти. При любом конечном быстродействии компьютера для решения теоретически решаемой задачи не хватит времени существования Вселенной (или не хватит объёма обозримой Вселенной для хранения промежуточных результатов). Существование сколь угодно трудных задач доказал в молодости (кажется, ему было всего 23 года тогда) один советский воспитанник новосибирского Академгородка по фамилии, кажется, Матиясевич (сейчас, кажется, где-то там - вдали от Академгородка и России вообще).

По аналогии можно предположить существование бесконечного количества постижимых идей. Некоторые из них человечество освоило, додумалось до них. До каких-то додумается в будущем. А до каких-то, вполне постижимых, не додумается никогда. Из-за нехватки времени. Человечество исчезнет раньше. Или потеряет интерес к познанию. Дегенерация.

Если мою телесную оболочку закопают в землю, а не распорядятся ею иначе, хочу, чтобы над ней росла урожайная яблоня. Пусть яблоки падают на головы российских платонов и быстрых разумом невтонов.

Comments

[Гость]

Существование сколь угодно трудных задач доказал в молодости (кажется, ему было всего 23 года тогда) один советский воспитанник новосибирского Академгородка по фамилии, кажется, Матиясевич (сейчас, кажется, где-то там - вдали от Академгородка и России вообще).



Прошу прощения за вторжение, но не смог пройти мимо. Хочу Вас немножко поправить. Юрий Владимирович Матиясевич родился, учился и работает по сей день в Ленинграде/Петербурге, где сейчас заведует лабораторией математической логики Математического института им. В.А. Стеклова (за границу, конечно тоже ездит, не без этого).

К новосибирскому академгородку отношения не имеет (хотя там действительно есть сильная школа математической логики). А прославился он решением 10ой проблемы Гильберта, доказав несуществование общего алгоритма, позволяющего разрешить любое диофантово уравнение. Теорией сложности вычислений он тоже интересуется, но прославился, как я уже сказал, не этим.



С большим интересом читаю Ваши заметки.



--- EKS (иногда заглядываю и на эсперантский форум).

[Старый чукотский солдат]

Гость Юрий Владимирович Матиясевич ... [к] новосибирскому академгородку отношения не имеет



Прошу прощения у Юрия Владимировича Матиясевича. Я или перепутал фамилию, или то был другой Матиясевич.

Где же эта брошюрка Трахтенброта, в которой я это прочитал?

А Трахтенброт, кажется, уехал...