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

Продолжаем тему усердного бобра. Начало👆

Придётся немного подумать: идея кажется простой, но на самом деле хитрая 🤔.

В статье «Bounds on the Rates of Growth and Convergence of All Physical Processes» Тоби Орд рассматривает любые измеряемые физические величины и показывает, что скорость их роста или убывания обязана находиться в определённых пределах ⏳.

Помните невычислимую функцию бобра BB(n)? Если бы физический процесс протекал с такой же скоростью, как функция бобра, мы могли бы вычислить BB(n) просто измеряя физические величины 📏. Но это невозможно, если принять физический тезис Чёрча–Тьюринга: любой физически реализуемый процесс можно смоделировать на машине Тьюринга 🤖.

Pаз машина Тьюринга не может вычислить BB(n), то и физический процесс не может вычислить BB(n) — то есть не может протекать
со скоростью BB(n) (см. доказательство тут).

Вы спросите: а почему бы физическим процессам не протекать быстрее функции бобра?

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

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

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

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

📌 Из этого вытекают целых восемь физических принципов, которые не следуют из известных законов природы. Они возникают только из логики — из тезиса Чёрча–Тьюринга и невычислимости 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

Сегодня в 19:00 по немецкому времени, в 20:00 по Киеву/Москве можем поговорить про усердного бобра 👆Вдруг кому случайно будет нечего делать в воскресенье вечером )

Вверху будет кнопочка «присоединиться к стриму»

стрим начался

я отойду на пару минут, всё равно по опыту нужно подождать пока люди подойдут

стрим сегодня был кратким, чётким и очень познавательным. отчёт следует. Не забываем, что стрим, где всем надо быть - 23-го июля! напоминание в песенном виде 👇

Дорогие друзья, специально для вас! Желаем вам отличных выходных и, как сказано в этом видео, таки следующий шикарный физмат-лайв-стрим с супер-крутыми гостями 23-го июля.

Официальный анонс скоро в этом канале.


#LiveStream #НастроениеСубботы #Culture

@easy_about_complex

1/2

🌀 Квантовая физика, здравый смысл и немного здоровой дерзости

Автор: М. Кацнельсон (Фейсбук)

Вот это всеобщее радостное бульканье о полной непостижимости квантовой физики... В общем, я совсем перестал понимать, что имеется в виду. Ох - соотношение неопределенности Гейзенберга! Вы только подумайте - квантовая частица не имеет одновременно точного значения координаты и скорости. Караул - спасите - хулиганы зрения лишают.

А что - то, что в классической механике задание координаты и скорости однозначно определяет движение - это вот прямо очевидно? Вот прямо проснулся в шесть часов, разобрался с пресловутой резинкой и сразу думаешь: ну да - законы движения представляют собой дифференциальное уравнение второго порядка, ежику понятно, не третьего ведь и не первого, значит, функция и производная нужны, чтобы определить задачу Коши. Проще некуда!

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

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

Классическая механика крайне противоинтуитивна и противоречит повседневному опыту, не зря ее придумывали тысячелетиями. Мы живем в мире где царит трение, Галилей и Ньютон - это больше про небесные тела (как это и было исторически), где вездесущие Божие сопротивления движению тел не оказывает, и которые в повседневный жизненный опыт широчайших рабочих и крестьян скорее не входят, нежели входят. А симплектическая геометрия фазового пространства? А принцип наименьшего действия со всей связанной телеологией? А - да чего там - вращательное движение? Есть известная фотография: Бор и Паули наблюдают за движением волчка и оба явно охреневают. А детерминистский хаос?

И это я еще молчу о вполне себе классической теории относительности.

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

В общем, ребята: квантовую механику не понимает никто (т.е., вы лично не понимаете) - ну ОК. А классическую физику вы понимаете? Правда-правда?

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

1/3
Немного о математических моделях в психологии принятия решений

Представьте, вам предлагают:
📍 Либо 50 долларов прямо сейчас,
📍 Либо 100 долларов через полгода.

Большинство людей выберут деньги сразу. Почему? Потому что:
— вдруг человек забудет или передумает платить;
— сейчас нужнее;
— и т.д.

Это логика: лучше воробей в руке, чем журавль в небе. И это называется снижением ценности будущего — чем дальше выгода, тем меньше она кажется нам ценной.

А теперь представьте, вам предлагают:
📍 Либо 50 долларов прямо сейчас,
📍 Либо 1 000 000 долларов через полгода.

Тут выбор большинства будет другой....

📉 Что говорит теория? Как смоделировать математически принятие нашим мозгом решений такого рода?

Изначально экономисты ожидали, что при оценке рисков и принятии решений мы уменьшаем ценность будущего по экспоненциальной формуле:

V(t) = V₀ · e^(–kt)

Где
V(t) — ценность через время t,
V₀ — ценность сейчас,
k — индивидуальный для для каждого из нас коэффициент «нетерпеливости».

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

2/3. Продолжение. Начало 👆

B 80-х Джордж Эйнсли провёл серию экспериментов. Людям задавали два почти одинаковых вопроса:

1️⃣
📍 $50 прямо сейчас
📍 $100 через 6 месяцев
→ большинство выбирает $50

2️⃣
📍 $50 через 3 месяца
📍 $100 через 9 месяцев
→ большинство уже выбирает $100

🤔 Что? Те же самые 6 месяцев разницы — но результат противоположный! Экспонента так не умеет. А вот гипербола — умеет:

  V(t) = V₀ / (1 + k·t)

Эта функция обесценивает ближайшее будущее быстрее, чем далёкое. Именно это мы и наблюдаем: сначала $50 сейчас кажется очень ценным. Но когда оба варианта в будущем — резкого «перетяга» уже нет, и $100 выигрывает.

Обе кривые на рисунке👆

Ещё пару моделей:в продолжении 👇

2/3. Продолжение. Начало 👆

Ещё пару моделей:

📍 Marshmallow Test (тест с зефиркой):
Ребёнку:
📍 один зефир сейчас
📍 или два через 15 минут
→ Тут включается сомнение, будет ли награда. Добавим вероятность:

  V(t) = (V₀ · p(t)) / (1 + k·t)

где p(t) — субъективная вероятность, что награду действительно дадут.

🎲 А если добавим риск, получим классическую ожидаемую полезность:

  EU = Σ pᵢ · u(xᵢ)

где:
— pᵢ — вероятность исхода i
— xᵢ — результат
— u(xᵢ) — его полезность (часто берут логарифм или корень)

🌀 А в Prospect Theory (Канеман и Тверски):

  V = Σ π(pᵢ) · v(xᵢ)

где:
xᵢ — возможный исход (например, +$100 или –$50)
v(xᵢ) — субъективная полезность этого исхода (выгоды воспринимаются логарифмически - меньше радости с каждым долларом, потери воспринимаются сильнее, чем выигрыши той же величины (loss aversion).
π(pᵢ) — субъективное восприятие вероятности (люди переоценивают малые вероятности и недооценивают большие)

📌 Всё это важно, потому что поведение людей — не идеально рациональное, но его можно описывать математически, если подбирать правильные функции: не только время, но и доверие, страх, риски, надежду. Но это очень сложно! Однако если вы поставите много-много лайков, то мы продолжим эту тему и расскажем при чём же тут нейросети 😂

@easy_about_complex

#MathModeling #Psychology

🧠 Лайв-стрим — 23 июля

В 18:00 по немецкому времени (19:00 по Киеву/Москве) у нас в гостях —
Михаил Коробко, старший научный сотрудник Института квантовой механики Университета Гамбурга и популяризатор науки.

Telegram-канал Михаила: @homeostatic_universe

📡 Стрим открытый — можно слушать, задавать вопросы и участвовать в разговоре.

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

📍Присоединиться можно будет 23 июля в указанное время — кнопка «Присоединиться к стриму» появится вверху этого канала.

🗓️ Отметьте у себя в календаре — будет интересно не только физикам.