Рождество и немного размышлений перед праздниками
Очень заумная история, которая длится даже не 2024, а целых 2324 года. 🎄📚

Если спросить людей, какая книга считается самой читаемой в мире, то раньше часто отвечали — Библия. 📖 Сейчас некоторые, возможно, скажут — Коран (который меня, честно говоря, в его радикальном проявлении мягко говоря, беспокоит 😬). Но оба эти ответа будут не совсем точными. Ведь ни Библию, ни Коран не читали все люди на планете. А вот есть книга, которая старше Библии примерно на 300 лет 📜 и, естественно, Коранa. Если её в оригинале читали единицы, то отрывки из неё в школе проходили абсолютно все — в любой стране и вне зависимости от вероисповедания. Угадали уже, что за книга? Или подсказывать? 😉

Уже более 2300 лет лучшие умы человечества ломают голову над этим трудом. И это не преувеличение! 🧠✨

Примерно в 300 году до Рождества Христова некий человек, которого звали Евклид из Александрии, решил понять, как устроен мир. Фигасе самоуверенность, подумаете вы, и будете абсолютно правы! 😄 Но давайте разберемся, как именно он подошел к вопросу мироустройства, какими шагами двигался к своей цели и, главное, что из этого вышло. И хотя эта история не завершена, кажется, она только начинается. 🚀

Евклид сделал следующее: он взял за основу эмпирические наблюдения и сформулировал их в виде десяти аксиом — постулатов. Всего десяти! 🔟 Затем он решил: "Теперь с помощью логики я выведу из этих десяти постулатов всё, что можно знать о мире". А в мире что вообще есть? Есть только пространство и время. Правда, на время Евклид замахиваться не стал — он сосредоточился на описании пространства. 🌌

Но была одна проблема — его пятый постулат. Этот постулат веками считали слишком сложным и "не таким очевидным, как остальные". 🌀 Разобраться с ним оказалось настолько сложно, что над ним ломали голову лучшие умы человечества. Гении, такие как Гаусс, Риман, Бойяи, Лобачевский, Минковский и другие, создали целые новые области математики, отталкиваясь от пятого постулата Евклида. Их работы привели к созданию неевклидовой геометрии и революционизировали наше представление о пространстве и времени. Через десятки и даже сотни лет их открытия стали основой для общей теории относительности Эйнштейна, которая связала пространство и время в одно целое. ✨ ⏳

Если кому интересно, то в одном из следующих сообщений я расскажу более подробно (и простым языком!) о том, над чем 2000 лет ломали голову лучшие математики. 🤓 Это история не только о математике, но и о эволюции человечества, о том, что движет и направляет эту историю.

Продолжение и детали следуют…

#Logic #Decidability #Computability

Рождество и немного размышлений перед праздниками: пятый постулат Евклида в действии 🎄🤔

Выше мы начали тему Евклида, который за 300 лет до Рождества Христова умудрился подбросить человечеству задачку с пятым постулатом: тут

Первый постулат Евклида звучит так: Через любые две точки можно провести одну прямую. Логично! ✔️ Остальные постулаты тоже ничего. Например, второй — любую прямую можно продолжить в обе стороны без ограничения. Понятно же? Понятно! 😌

Однако знаменитый пятый постулат (постулат о параллельности) задал задачку. Звучит этот 5-й постулат так:

Если прямая пересекает две другие прямые так, что сумма внутренних углов на одной стороне меньше двух прямых углов, то эти две прямые, если их продолжить, пересекутся на той стороне, где сумма углов меньше двух прямых углов. 🔺📐

Как вам? Нравится? 🤨 Вот и никому не нравилось! Почему девять постулатов (аксиом) такие простые, а этот 5-й какой-то корявый и сложный?! Может его выбросить нафиг? ❌ Останется не 10, а 9. Мало шо-ли? Какая разница, одним больше — одним меньше, или есть разница? 🤷‍♂️

Что будет, если его выбросить, как думаете? 💭 Прежде чем мы перейдём к физике, которая следует из 5-го постулата Евклида, пишите в комментариях, что будет, если пятый постулат убрать вообще. ✍️

Гусары математики молчать! Mнения людей, которые вообще не математики, приветствуется! 🤗 Пишем в комментариях, не стесняемся!

А математикам такой вопрос: что будет, если заменить 5-й постулат на любую из теорем евклидовой геометрии, которые с помощью него доказываются 🤔 🧩

Продолжение и детали следуют…

#Logic #Decidability #Computability

🧠 Может ли человеческий мозг быть супер-Тьюринг-машиной?

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

📌 Что такое модель Тьюринга (простыми словами):
Это математическая идея, которая описывает всё, что можно вычислить на любом компьютере — неважно, насколько он мощный или современный.
Если задачу можно формализовать как алгоритм, её можно решить в рамках модели Тьюринга. Это как фундамент всех программ и цифровых вычислений.

🧠 Но вот главный вопрос:
А может ли человеческий мозг решать задачи, которые невозможно выразить как алгоритм, т.е. которые нерешаемы в моделе Тьюринга?
Может ли он быть сильнее, чем любая возможная программа или компьютер?

📌 Хава Зигельман (Hava T. Siegelmann) предложила модель нейронных сетей, которые при использовании вещественных (реальных) весов могут решать задачи, не поддающиеся алгоритмизации. Это явление называется супер-Тьюринговыми вычислениями.

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

🔍 В научном сообществе идут активные споры:

💡 Сторонники утверждают:

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

⚠️ Скептики возражают:

- Вещественные числа нельзя физически представить с бесконечной точностью.
- Мозг работает в условиях шума и ограниченности.
- Пока нет доказательств, что биология способна выйти за пределы модели Тьюринга.

📚 Если интересно глубже — вот несколько ключевых работ:

Siegelmann (2003): Нейронные и супер-Тьюринговые вычисления
Wiedermann (2012): Аргумент против сверхинтеллекта
Cabessa & Siegelmann (2014): Супер-Тьюринг нейронные сети

🧩 Вывод:
Если мозг действительно способен на супер-Тьюринговые вычисления — это может полностью изменить наши представления о разуме и искусственном интеллекте. Но пока это — гипотеза, ожидающая доказательств.

✍️ А вы что думаете? Можем ли мы мыслить за пределами алгоритмов?

✍️ пару выдержек из этих работ оставлю в комментариях, чтобы не потерять

#Computation #Computability #Complexity #Turing #Brain

@easy_about_complex

🧠 Есть и другой смысл в невычислимости по Тьюрингу…

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

⚠️ Например, говорят: "Проблема остановки неразрешима."
Что это значит?

💡 Что такое проблема остановки?
Допустим, у нас есть любая программа и входные данные. Вопрос:
📍 Остановится ли программа, или будет работать вечно?

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

⚠️ Нюанс: это не значит, что все случаи неразрешимы!
- Есть много программ, для которых можно сказать, остановятся они или нет.
- Есть даже целые подмножества, где эта задача решается легко(например, программа без циклов).

👉 Невычислимость — это свойство класса, а не каждого конкретного случая. То есть не существует одного алгоритма, который сработает всегда.

🧠 И вот в чём суть:
Может ли мозг решать задачи по одной, интуитивно, без универсального алгоритма?
Если да — может ли он выйти за пределы Тьюринга?

Отмечу, что человек решает конкретные задачи из классов, которые невычислимы по Тьюрингу...

Интересно? Глубже разберём в следующих постах.

#Computation #Computability #Complexity #Turing #Brain

Продолжение. Начало тут.

Ведь если бы казнь была в субботу, вы бы уже знали об этом в пятницу! Дальше! Пятница? Нет, если бы казнь была в пятницу, вы бы уже знали об этом в четверг!»

Адвокат продолжает, выстраивая логику, день за днём, исключая каждый возможный день недели. «Понедельник? Тоже нет. Если бы казнь была в понедельник, то вы бы узнали об этом в воскресенье!» 😅

Но вот вопрос: что же не так в этой логике? 🤨

Парадокс не в том, что адвокат ошибается, а в том, что само условие казни и способ её определения создают замкнутую, противоречивую ситуацию. И в какой-то момент вы вдруг понимаете, что казнь всё-таки может состояться — и произойдёт в любой день, когда заключённый не будет об этом знать заранее. 😱

Продолжение и связь с пределами вычислимости, теоремой Гёделя следует…

#Logic #Decidability #Computability #Philosophy

@easy_about_complex

2/2. Продолжение. Начало тут


🧠 А что насчёт мозга и нейросетей?
Тут как раз интересно. В 90-х Сигельманн с коллегами показали, что:

Любая Тьюринговая машина — это частный случай рекуррентной нейросети.

Сеть с рациональными весами (всего 886 нейронов!) может вычислить все частично-рекурсивные функции 👉 ссылки на публикации тут

А если веса вещественные — вычислительная мощность может выйти за пределы Тьюринга (и при этом в модели не требуется бесконечная точность, достаточно линейной. Hо тут есть нюанс! Mожет быть обсудим на одном из следующих стримов).

📐 Ключевая идея:

непрерывность (вещественные числа и аналоговые процессы) может не просто приближать реальность, а давать качественно новые вычислительные возможности. Хотя на практике мы не можем задать числа с бесконечной точностью, сама природа, как кажется, оперирует реальными значениями (π, G, массы планет и т.д.) независимо от нашей способности их измерить.

📊 Исследования даже показали, что между рациональными и вещественными весами в нейросетях лежит целая иерархия вычислительных классов. Суть в информационной сложности чисел, которая измеряется через ресурсно-ограниченную колмогоровскую сложность.

📌 Вывод: Мы не знаем, вычислима ли физика. Возможно, вся Вселенная — гигантский алгоритм. А может, где-то в её глубинах живёт настоящая невычислимость, просто мы её ещё не нашли.

Так что, по состоянию на сейчас:
Физический мир может быть вполне вычислим. А может и нет. ¯\_(ツ)_/¯

Если найдут настоящий физический феномен, где вычисление результата принципиально невозможно — это будет просто бомба. А пока… можно только моделировать невычислимость внутри математики, но не в лаборатории.

#Decidability #Computability #Turing #Physics #Brain #Philosophy

продолжение. начало тут.

Что показал Кристофер Мур:
— Система с тремя степенями свободы (например, частица в 3D-потенциале) может эмулировать Тьюринг-машину.
— Даже если начальные условия известны точно, всё равно невозможно ответить на многие вопросы о будущем поведения системы.
— Это не просто хаос (чувствительность к начальным данным), а глубинная невычислимость — фундаментальное ограничение, заложенное в математике.

🤯 Другими словами: можно построить закон движения, в котором "спрятана" неразрешимая задача, т.е. проблема остановки.

Формально — это уже физика, но физика, искусственно усложнённая до машины Тьюринга.

🌀 Теперь главный философский вопрос:

А если физика и вычислима, но вычисления займут больше времени, чем возраст Вселенной?

С практической точки зрения — это почти то же самое, что невозможность вообще. Модель может быть "вычислимой", но если тебе надо 10⁸⁰ шагов, чтобы узнать будет ли частица тут или там — на что тебе это знание?

То есть граница вычислимости — это не только "можно/нельзя", но и "успеть/не успеть".

📎 Вывод:

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

Возможно, законы Вселенной написаны на языке, который мы теоретически понимаем — но читать на нём практически невозможно.

#Decidability #Computability #Turing #Physics #Brain #Philosophy

📐 Интегралы, которые невозможно выразить в элементарных функциях

После этого поста стало очевидно, что дорогие читатели этого канала очень любят интегралы.

А вот знаете ли вы, что далеко не все интегралы можно выразить через "обычные" функции вроде синуса, экспоненты или логарифма? Например, классический интеграл

∫𝑒^{−𝑥^2}𝑑𝑥

не имеет выражения через элементарные функции. Его значение задаётся через специальную функцию — ошибку Гаусса (erf).

🔍 Это открытие уходит к работам Жозефа Лиувилля в 1830-х годах. Он доказал теорему существования первообразной в элементарных функциях для определённых видов подинтегральной функции. Но нам же мало знать, что интеграл можно взять? Мы хотим его вычислить алгоритмически!

🧠 В 1969 году Роберт Риш разработал алгоритм (ныне известный как алгоритм Риша), который позволяет автоматически определить, можно ли взять интеграл в элементарных функциях. Этот алгоритм лёг в основу современных систем компьютерной алгебры: Mathematica, Maple, Maxima.

📚 Среди других ключевых работ:
– Бронштейн (1997) — систематизация алгоритмических методов
– Барри Трейгер (1984) — интегралы от алгебраических функций
– Теория "fewnomials" Хованского — на стыке алгебры и анализа

💡 Примеры неэлементарных интегралов:
– ∫sin⁡(𝑥^2)𝑑𝑥
- ∫sin(𝑥)/𝑥𝑑𝑥
- ∫sqrt(1+𝑥^3)𝑑𝑥

Такие выражения требуют специальных функций — от Bessel до эллиптических, и создают мост между алгеброй, анализом и математической физикой.

✳️ Вывод: даже простые на вид интегралы могут скрывать глубокие слои математической теории.

#ODE #ComputerAlgebra #Computability #Algorithms

@easy_about_complex

2/3. Начало тут 👆

Важно: функция BB(n) невычислима, то есть не существует алгоритма, который мог бы точно вычислить её значение для всех n. Доказывается это через проблему остановки. Чтобы вычислить BB(n) для машин с n состояниями нам по-любому надо определить какие машины не останавливаются. Это, увы, не вычислимо.

📈 Более того, BB(n) растёт быстрее, чем любая вычислимая функция.

🔍 Как это доказывается?

Представим, что у нас есть вычислимая функция f(n), которая, предположим, растёт быстрее, чем BB(n). То есть:
f(n) > BB(n) начиная с какого-то n, и при этом разница f(n) − BB(n) стремится к бесконечности при n → ∞.

Но тогда мы можем использовать f(n), чтобы вычислить BB(n):

- Сгенерировать все машины Тьюринга с n состояниями (их конечное число).

- Симулировать каждую не более чем f(n) шагов (по нашему предположению этого достаточно, чтобы все, кто должны остановиться, уже остановились по определению BB(n)).

- Из всех остановившихся выбрать ту, которая делала максимум шагов — и получить BB(n).

👉 Но это противоречит тому, что BB(n) невычислима. Следовательно, никакая вычислимая функция не может расти так быстро как BB(n).

🌌 А теперь — самое интересное:

Если предположить, что всё в физическом мире алгоритмизуемо (то есть, физический тезис Чёрча–Тьюринга верен и вселенная — это в каком-то смысле алгоритм) тогда из доказательства выше следуют 8 новых физических принципов, о которых мы расскажем завтра.

Пока кратко: усердный бобр и BB(n) ограничиваeт, как быстро или насколько медленно может расти или сходиться любая измеримая физическая величина.

💥 Эти принципы не следуют из известных физических принципов или законов.

Вот pабота про это:
🔗 Bounds on the rates of growth and convergence of
all physical processes

💬 Если тезис Чёрча–Тьюринга верен ∧ за физическими процессами скрываются алгоритмы в том или ином виде, то физические процессы вдруг оказываются ограниченными не только симметриями, энергиями и скоростями, но и границами вычислимости и из них следуют новые физические принципы, которые не так уж и очевидны.

Как по мне, то глубокая связь между информатикой и естественными науками.

Продолжение 👇

#Computability #Turing #Physics #Beauty

Продолжение. Предыдущая часть тут 👆

Дело в том, что легко показать: все функции растущие быстрее функции бобра - тоже невычислимы ⚠️

Если бы физические процессы протекали с этими скоростями - мы могли бы вычислять невычислимые функции просто производя измерения физических величин.

📌 Из этого вытекают целых восемь физических принципов, которые не следуют из известных законов природы. Они возникают только из логики — из тезиса Чёрча–Тьюринга и невычислимости BB(n).

Тоби Орд вводит ещё трёх персонажей, дополняющих нашего замечательного бобра. Итак, у нас есть:

1. Усердный Бобр (Busy Beaver, BB(t))
→ максимальное число шагов останавливающейся машины Тьюринга с t состояниями. Это верхняя граница роста: если тезис Чёрча–Тьюринга верен, ничто во Вселенной не может расти быстрее. Ни расширение вселенной после большого взрыва, ни искривление пространства-времени при приближении к сингулярности в центре чёрной дыры. Ничего вообще.

2. Сонный Ленивец (Sleepy Sloth, SS(t) = BB⁻¹(t))
→ обратная функция к BB(t). Если BB(t) растёт невероятно быстро, то SS(t) — невероятно медленно. Нижняя граница роста 🐌. Если бы период колебаний системы увеличивался так катастрофически быстро, что его частота (то есть 1/период) уменьшалась бы медленнее SS(x) - такого не может быть в природе, это запрещено.

3. Асимптотический Ахиллес (Asymptoting Achilles, AA(t) = 1 / BB(t))
→ стремится к нулю очень быстро. Это верхняя граница скорости сходимости: никакой процесс не может приближаться к пределу быстрее, чем AA(t) 🏃‍♂️💨. Если вы сжимаете газ, его объём не может уменьшаться к нулю быстрее, чем AA(x), даже при бесконечном давлении. Скорость любого процесса, приближающегося к стабильному состоянию, имеет верхний предел.

4. Медлительный Мечтатель (Dawdling Daydreamer, DD(t) = 1 / SS(t))
→ стремиться к нулю очень медленно. Нижняя граница скорости сходимости: даже самые медленные приближения к равновесию не могут быть медленнее, чем DD(t) 🐢. Процесс химической реакции не может "замирать" на долгое время, оставаясь вдали от равновесия. Должен быть минимальный темп приближения.

5-8: Принципы 5, 6, 7 и 8 я пока что опущу, но если вы напишете в комментариях, что хотите, то можем и их разобрать либо в комментариях к этому посту письменно, либо на нашем традиционном онлайн-стриме.

✨ Кстати, напомню, следующий онлайн-стрим с очень крутыми гостями как раз из физики - 23-го июля вечером! Официальный анонс следует!

🧠 💪 А пока предлагаю всем читателям доказать в качестве простого упражнения:

- любая функция, которая растёт быстрее BB(n) - невычислима
- функции BB⁻¹(n), 1/BB(n) и 1/BB⁻¹(n) - невычислимы


Анализ и выводы из этой темы следуют скоро 👇

@easy_about_complex

#Computability #Physics #Logic #Philosophy #Turing #LiveStream