Есть ли "предел" сложности ?

[shkolnik]

Трудно сразу и кратко сформулировать вопрос темы, начну с примера.
Например, мы изучаем физическую систему, состоящую из частиц. С одной стороны, мы приходим к классической механике, с другой, к термодинамике. В обоих случаях это теории, описывающие одну и туже физическую систему. Теории состоят из постулатов (аксиом), логических правил вывода одних утверждений из других, математических правил обращения с числами, методов и т.д. Возможно, в контексте темы, проще полагать теории просто алгоритмами, работа которых способна описать изучаемую физическую систему. Сложность этих алгоритмов (теорий) можно оценить, например, по Колмогорову. Соответственно, и сложность физической системы (как набора входных данных для алгоритма) тоже поддается такой оценке.
Увеличивая количество частиц, мы вроде бы увеличиваем ее сложность, при этом сложность описательного алгоритма (теории) не меняется. Конечно, физическая система может стремится к масштабной инвариантности, например, частицы объединятся в объекты, обладающие теми же свойствами, что и сами частицы. В терминах входных данных, это означает повторяемость, наличие закономерности в последовательности. Тогда функция сложности по шкале масштабов будет неизменной или периодичной.
Однако, чаще, физические системы такой инвариантностью не обладают и путешествие по шкале масштабов, открывают в системе новые свойства, которые не описываются предыдущими теориями (алгоритмами). В этом случае создаются новые теории (алгоритмы), которые описывают уже эти свойства. Как, например, теория относительности или квантовая механика.
Возможно, в системе на тех же масштабах, открываются новые свойства, ранее не описываемые существующими теориями (алгоритмами), например, электрические и магнитные свойства частиц. Создается новая теория(алгоритм) их описывающая, электродинамика. Или элементы системы демонстрируют настолько нетривиальное поведение, что для его описания требуется отдельная теория (алгоритм), например, химия, биология и т.д.
Мне кажется, что сложность каждой по отдельности такой теории (алгоритма) сопоставима и не сильно разнится. У всех у них несколько разные объекты, предметы, методы, но, в сущности, они одинаково сложны, в каком-то алгоритмическом смысле.
Если мы начнем брать физические системы на максимальном разбросе масштабов, с максимальным количеством свойств и описывать их как целое, то мы будем объединять различные существующие теории (алгоритмы) в один большой алгоритм (теорию).
Мне почему-то представляется, что она вряд ли окажется сложнее, чем каждая из ее составляющих по отдельности. Именно потому, что каждая теория сама по себе сложна и сопоставима по сложности с другой. Их отличие не в сложности, а в объекте, предмете, методе.
Вопрос состоит в том, будет ли сама физическая система (входные данные), которую призваны описать все эти алгоритмы (или один единый алгоритм) все более сложной ?
Как пример: что сложнее галактика или циклон ? живая клетка или человеческая цивилизация ? биосфера или человеческий мозг ? и т.д. и т.п. Соответственно: что сложнее биология или физика ? химия или кибернетика ? экономика или право ? и т.д. и т.п.
Таким образом, основные вопросы темы: ограничены ли сверху по сложности материальные системы (входные данные) и наши теории (алгоритмы). Можно ли считать, что "предел" сложности вытекает из невычислимости функции сложности ?

[epros]

shkolnik в сообщении #1041757 писал(а):

ограничены ли сверху по сложности материальные системы (входные данные) и наши теории (алгоритмы)

Попробуйте начать с определений. В частности: что такое "сложность"? Можно на каком-нибудь примере, скажем, насколько сложна арифметика натуральных чисел (для определённости возьмём аксиоматику Пеано первого порядка). Я не понимаю, как Вы собираетесь оценивать её "сложность", если:
1) С одной стороны, всю аксиоматику можно уложить в несколько строк предельно формализованного текста.
2) С другой стороны, эта теория позволяет (теоретически) выполнять такие операции, как разложение на простые множители чисел в миллионы разрядов, что силами всех вычислительных мощностей человечества невозможно посчитать за всё время существования Вселенной.

[atlakatl]

shkolnik в сообщении #1041757 писал(а):

Если мы начнем брать физические системы на максимальном разбросе масштабов, с максимальным количеством свойств и описывать их как целое, то мы будем объединять различные существующие теории (алгоритмы) в один большой алгоритм (теорию).
Мне почему-то представляется, что она вряд ли окажется сложнее, чем каждая из ее составляющих по отдельности. Именно потому, что каждая теория сама по себе сложна и сопоставима по сложности с другой. Их отличие не в сложности, а в объекте, предмете, методе.

Вспоминается сократовское: «Один дурак может задать столько вопросов, что на них не ответит и сотня мудрецов».
Любую ситуацию, объект или явление можно – субъективно – усложнить сколь угодно много.
Ваша – не Колмогоровская – сложность это просто праздный поиск всё новых свойств у феномена. В жизни сложность ограничивается практикой: кому-то вождение автомобиля легко и естественно, а общение с малознакомой женщиной вводит в ступор. И наоборот.
Хочешь, но не можешь – проблема сложная. Пофиг и не можешь - … да никакой сложности нет и в помине!
Предел хотения чего-то или кого-то ограничивается нашим жизненным опытом. А значит и сложность стоящих перед нами проблем конечна.

[fedotv]

Цитата:

Есть ли "предел" сложности ?

Вы пытаетесь описать "Проекционные итерационные методы решения уравнений" - словами, потому так много неточности.
Сложность(предел) ограничен, только, числом членов в вашем базисе(сознании), как смогли спроецировать, как и понимаете. Все просто.

P/S Книжек мало по теме, но есть.

[fedotv]

Вероятно, с развитием этой области математики, появятся новые возможности(улучшатся старые).
Можно будет строить модель сознания человека, описывать его машине, делать прогнозы поведения, развития с более высокой точностью, чем при сегодняшних методах(психологических итд). Вносить корректировки. Появятся новые услуги, как сегодня "Генетическая дактилоскопия", https://www.genotek.ru/ - итд

P/S Будут новые "Клиники - мозговеды"
И новые, связанные проблемы, тоже.

[Munin]

shkolnik в сообщении #1041757 писал(а):

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

Это всего лишь свойство людей, которые придумывают теории, описывающие системы. Люди не могут придумать слишком сложную теорию (или могут, но в несколько этапов, что вы назовёте несколькими теориями).

[Korvin]

Munin в сообщении #1042001 писал(а):

shkolnik в сообщении #1041757 писал(а):

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

Это всего лишь свойство людей, которые придумывают теории, описывающие системы. Люди не могут придумать слишком сложную теорию (или могут, но в несколько этапов, что вы назовёте несколькими теориями).

А также объединять несколько теорий в одну, самый наглядный пример вузовские (для прикладников) и школьные курсы.

[shkolnik]

epros в сообщении #1041885 писал(а):

Попробуйте начать с определений. В частности: что такое "сложность"? Можно на каком-нибудь примере, скажем, насколько сложна арифметика натуральных чисел (для определённости возьмём аксиоматику Пеано первого порядка). Я не понимаю, как Вы собираетесь оценивать её "сложность", если:
1) С одной стороны, всю аксиоматику можно уложить в несколько строк предельно формализованного текста.
2) С другой стороны, эта теория позволяет (теоретически) выполнять такие операции, как разложение на простые множители чисел в миллионы разрядов, что силами всех вычислительных мощностей человечества невозможно посчитать за всё время существования Вселенной.

Сразу дать определение нереально. Попробуем с Вашим примером. Всю аксиоматику можно уложить несколько строк формализованного текста. При этом аксиомы – это инструкции алгоритма всех возможных доказательств в арифметике. Эти инструкций носят не предписывающий характер, а разрешающий. Т.е. это не совсем команды, в классическом алгоритмическом понимании, их можно применять, но последовательность применения неизвестна. Обойдем эту трудность следующими способами. Во-первых, существуют универсальные алгоритмы проверки доказательств. Т.е. если есть некая формула арифметики, алгоритм проверяет, выводима ли она из аксиом. Во-вторых, можно построить алгоритм, который будет выводить из аксиом, согласно правил математической логики, все утверждения арифметики, какие только возможны. Отвлечемся от того, что на каждом шаге будет чудовищное ветвление и возможно некоторые утверждения придется порождать генератором случайных чисел и уже затем регрессивно пытаться свести к аксиомам или опровергнуть. Т.е. теоретически нет никаких ограничений.
Ваш пример натолкнул меня на такую банальную мысль. Теории, в которых есть бесконечность (в арифметике это множество натуральных чисел), сложнее теорий, в которых ее нет. Что касается дальнейшего различения бесконечностей, например, по мощности, сомневаюсь, что они сложнее друг друга, это похоже на продолжение процесса ветвления всех возможных выводов из аксиом, просто добавлена генерация новых аксиом, которые "сложности" не привносят. По крайне мере, на каком-то этапе, все эти теории становятся похожи на хаос, где какая-либо аксиома, утверждение или его отрицание, перестают нести какую-либо смысловую нагрузку или начинают повторять сложность составных частей. Процесс генерации утверждений можно продолжать и дальше, но в лучшем случае его придется рассматривать, как "физический", ушедший от равновесия, применяя к бурлящей массе утверждений какие-то статистические, термодинамические методы, без надежды использовать их по назначению. Все равно, что забыть значение слов языка. Это можно было бы назвать пределом теоретической "сложности".
Что касается второго пункта, практической реализации, где "сложность" привязана к физике через теоретическое количество машин и тактов. Мне не известно, насколько простирается различимость классов сложности в иерархии P, NP… наступает ли на определенном этапе эквивалентность, неразличимость, или нет. Существует ли самая сложная задача (класс задач) и если да, интересно было бы посмотреть на хотя бы одну из них. Хотя сам факт их существования, говорил бы о существовании ограничения на сложность физических систем.

Munin в сообщении #1042001 писал(а):

Это всего лишь свойство людей, которые придумывают теории, описывающие системы. Люди не могут придумать слишком сложную теорию (или могут, но в несколько этапов, что вы назовёте несколькими теориями).

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

fedotv в сообщении #1041937 писал(а):

Сложность(предел) ограничен, только, числом членов в вашем базисе(сознании), как смогли спроецировать, как и понимаете. Все просто.

Переформулирую вопрос для Вас: ограничен ли чем-либо базис сознания (не моего, а в принципе), есть ли иерархия классов этих базисов и существует ли "предел" ?

[Dmitriy40]

Не совсем понял что Вы называете сложностью теории. Если только лишь её формулировку, то выше прекрасный пример с простыми числами и арифметикой.
А если множество описываемых явлений, то при комбинации двух разных теорий кроме объединения множеств явлений каждой вылезёт ещё огроменное множество взаимных эффектов/явлений (не зря же синергетику пытаются выделить в отдельную науку). Как пример, если есть теории описывающие сопротивление, ёмкость и индуктивность по отдельности в электрических процессах, то при соединении их вместе появляется куча резонансных эффектов, как бы не на порядок сложнее.

Про химию, биологию, геологию и прочие, по идее они все выводятся из квантовых теорий. Но очень сложно. Оказалось гораздо проще не брать на каждый чих интегралы по всем $N_A$ (число Авогадро) частицам, а написать сразу уравнение макросостояния всего объекта. До некоторого предела оно описывает поведение объекта достаточно точно. И так почти со всем.

Ну и про предел сложности. Если чисто теоретически, то вероятно он есть. Только что толку? В качестве такого предела можно взять количество элементарных объектов во Вселенной, описать все их свойства, правила взаимодействий (всего-то 4 силы пока известно) - и получить "теорию" (в Вашем смысле), описывающую всё происходящее во Вселенной. И из неё же будут выводиться (как следствия) все наблюдаемые и все возможные явления, хоть в химиии, хоть в психологии. Ничего сложнее этой "теории" не нужно, так что её вполне можно считать пределом сложности. Хотя очень и очень многие интересные вещи в неё могут и не войти, например всё с бесконечностями в любом виде, да даже $\sqrt{2}$ ей не описывается абсолютно точно.

[shkolnik]

Dmitriy40 в сообщении #1043290 писал(а):

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

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

Dmitriy40 в сообщении #1043290 писал(а):

Про химию, биологию, геологию и прочие, по идее они все выводятся из квантовых теорий. Но очень сложно. Оказалось гораздо проще не брать на каждый чих интегралы по всем $N_A$ (число Авогадро) частицам, а написать сразу уравнение макросостояния всего объекта. До некоторого предела оно описывает поведение объекта достаточно точно. И так почти со всем.

Просто объекты, методы, принципы у этих теорий разные. В стартовом сообщении я писал про механику и термодинамику, разве одна сложнее другой ?

Dmitriy40 в сообщении #1043290 писал(а):

В качестве такого предела можно взять количество элементарных объектов во Вселенной, описать все их свойства, правила взаимодействий (всего-то 4 силы пока известно) - и получить "теорию" (в Вашем смысле), описывающую всё происходящее во Вселенной.

Может быть, некоторая корреляция между сложностью и количеством элементарных объектов, числом сил, во Вселенной есть, но вряд ли она однозначная. Когда читал про антропный принцип, упоминалась, что изменение значения мировых констант, постоянной тонкой структуры, на ничтожные величины делает невозможной образование атомов и соответственно, звезд, планет, жизни и т.д. Т.е. при том же количестве элементарных частиц и сил, никаких сложных структур во Вселенной не образовалось бы. С другой стороны, когда мы смотрим на те, или иные структуры во Вселенной, мы можем разбить их на группы примерно одинаковой сложности. При этом чего-то сверхсложного не наблюдается. Т.е. наблюдаются объекты, структуры, явления, из разнообразных областей, сложность которых примерно одинакова и максимальна.
Можно связать сложность со случайностью, с энтропией, но это немного не то. Нельзя сказать, что минимальная энтропия соответствует максимальной сложности и наоборот. Как нельзя сказать, что одна случайная последовательность сложнее другой случайной (иначе они не случайны).

[Dmitriy40]

shkolnik в сообщении #1043294 писал(а):

Разве это происходит не потому, что теория достигает предела сложности ?

Нет. Именно из-за объединения разных теорий, каждая из которых сама по себе простая (в смысле объёма описываемых явлений), а результат объединения - на порядок (порядки) сложнее и разнообразнее. И да, если сравнивать сложность резонансных явлений и простого сопротивления (ёмкости, индуктивности), то первое во много раз сложнее. По сравнению с общей теорией они конечно обе где-то в низу шкалы сложности, но вот между собой они вовсе не одинаковы по сложности. Можно ещё такой пример привести: из ТФКП можно выделить как ТФДП (в действительных числах), так и арифметику, но Вы же не будете утверждать что они обе одинаковой или даже хотя бы сравнимой сложности?

Насчёт взаимной сложности Вам правильно выше написали что это может быть связано с именно таким построением теорий человеком, его ограниченностью.

shkolnik в сообщении #1043294 писал(а):

Может быть, некоторая корреляция между сложностью и количеством элементарных объектов, числом сил, во Вселенной есть, но вряд ли она однозначная.

А однозначности и не нужно, нужно лишь ограничение сверху, именно про него я говорил.
Корреляция же есть обязательно, каждый новый добавляемый в систему объект как минимум увеличивает размер описания состояния системы, а ведь ещё и его связи с остальными объектами надо учитывать.

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

PS. Всё же определитесь с понятием сложности, что Вы под ним подразумеваете, сложность формулировки или сложность описываемых явлений? Или что-то третье? Это принципиально.
Даже для алгоритмической сложности есть некий предел (алгоритм, для которого невозможно за конечное время доказать вычислим ли он вообще), что уж говорить про более общие теории.

[grizzly]

shkolnik
Хотелось бы лучше понять, какой смысл Вы вкладываете в свои слова и вопросы. Поэтому я зайду с другой стороны. Я предлагаю нам рассмотреть упрощённый вариант Вашего вопроса. Вместо физического мира возьмём ряд натуральных чисел, вместо теорий -- закономерности, которые можно из него извлечь (для более полной аналогии мы могли бы объединять эти закономерности в группы, но предлагаю не усложнять).

Мы можем некоторым образом количественно оценивать "сложность" этих закономерностей. (Как оценивать -- отдельный вопрос, но мы к нему можем вернуться позже, если сойдёмся в целом.) Новые закономерности мы можем описывать либо с чистого листа, либо на базе найденных ранее закономерностей (это тоже не важно).

И теперь я хочу предложить Вам такие переформулировки Ваших вопросов:
Будет ли наше представление о натуральном ряде, который призваны описать все эти закономерности, становится всё более сложным? Как пример: что сложнее числа Фибоначчи или числа Каталана? простые числа или совершенные? треугольник Паскаля или Пифагоровы тройки? и т.д. и т.п. Аналогичные вопросы можно задать и про сгруппированные закономерности (подобно химии, физике и т.п.).
Таким образом, основные вопросы темы: ограничены ли сверху по сложности подмножества натурального ряда (входные данные) и наши закономерности? Можно ли считать, что "предел" сложности следует из невычислимости функции сложности?

Видите ли Вы непреодолимую разницу между Вашим вариантом и такой переформулировкой? Если нет, то нам нужно теперь обсудить, как мы будем оценивать сложность. Я думаю, что мы можем выбрать очень простые способы оценки, не привлекая колмогоровской сложности -- тогда ответы на основные вопросы станут вообще тривиальными.

[epros]

shkolnik в сообщении #1043279 писал(а):

Попробуем с Вашим примером.

Ну, попробовали. И к чему пришли? Какую сложность Вы припишете арифметике Пеано первого порядка? Я пока не вижу вариантов решения, поэтому понятие "сложности теории" пока остаётся неопределённым.

Вы не подумайте, что я в принципе против. Идея как-то измерять сложность теорий -- сама по себе неплохая. Тем более, что "естественный отбор", который они проходят на практике, очевидно, производится в том числе и по каким-то критериям сложности. Т.е. простая теория с той же предметной областью заведомо предпочтительнее. Но что именно измерять? Вот в чём вопрос... С одной стороны, есть объём памяти, который потребуется для того, чтобы записать и хранить аксиоматику. Очевидно, что если теория "слишком сложна" по этому показателю, то её никто не станет использовать. С другой стороны, простота аксиоматики не гарантирует простоту выводов. Т.е. до некоторых выводов придётся добираться настолько долго, что может быть проще было бы сразу внести их в аксиоматику (и не экономить слишком на объёме памяти для её хранения). И есть живой пример этого в виде той же арифметики натуральных чисел: Все в школе учат наизусть таблицу умножения, хотя в аксиоматике Пеано ничего подобного нет, потому что вся таблица умножения -- вообще-то выводима из аксиом Пеано. Но какой же школьник будет выводить $6 \times 7 = 42$ из аксиом Пеано? Для него это -- слишком сложно.

(Оффтоп)

Я тут, сидя в очереди в одном учреждении, ненароком подслушал рассказ о чьём-то знакомом, которого все считали необычайно умным по той причине, что он доказывал $2 \times 2=4$ "с помощью кванторов" (слушатель с благоговением спрашивал: А что это такое?), исписав своим доказательством половину доски.

[Мастак]

shkolnik,
вот пределы понимания определенно есть, причем у каждого - свои пределы, причем только на конкретный момент

А сложность само собой разная везде и неопределяемая формально.
"Сложностью" алгоритмов (NP, P, ...) уже давно называют не сложность, а трудность (более корректно).
PS Предел - более формализуемое понятие, но предел чего - предел чего-то неопределенного неопределенным останется.

имхо

profrotter:
Предупреждение за систематическую публикацию бессодержательных сообщений.

(Подробно)

Forum Administration в сообщении #27356 писал(а):

I. Нарушения и санкции
1) Нарушением считается:
ж) Оффтопик, флуд, троллинг, размещение заведомо бессодержательных сообщений и тем, увод дискуссии в сторону от основного обсуждения, размещение большого числа сообщений в пределах одной темы подряд. Создание тем в стиле личного блога, не предполагающих обсуждения какого-либо вопроса. Искусственное поднятие темы бессодержательными сообщениями.

[Formular]

Задача решается чисто логически просто - надо определить сложность физической системы.
Физическая система дана объективно, природой, и чтобы определить её сложность, должен быть образец, стандарт, мера сложности, данная также объективно. Но природа не дала нам сложность как объективное явление навроде физической системы атома, молекулы, кристалла, Земли, звезды, и т.д. Сложность, это явление исключительно нашей рассудочной деятельности, нашего мышления, а потому, в отсутствии объективной меры сложности, оценка её может быть только субъективной. Поэтому "предел" сложности также может быть только субъективным понятием, и поэтому, в свою очередь, является несоизмеримым с любой другой оценкой сложности.