🌊🔢НАВЬЕ—СТОКС и ПРОБЛЕМА ОСТАНОВА. Часть 2. Вычислимость в физических системах В прошлом посте мы поженили гидродинамику и вычисления. Близко к цели, но пока еще не прямая связь с проблемой останова. Чтобы приблизиться ещё на один шаг нам нужны не простые жидкостные вычислители, нам нужен аналог универсальной машины Тьюринга. 💬На самом деле Теренс Тао был далеко не первым, кто пытался связать физические системы с универсальными вычислителями. Как писал Р. Пенроуз в своей книге Новый ум короля: - “Неразрешимость проблемы останова самим своим существованием породила естественные вопросы: какие физические модели способны к универсальным вычислениям и, следовательно, демонстрируют неразрешимые явления? Какие типы физики могут выйти за рамки вычислений?” Примерами физических задач, где, как было показано, возникает такая сложность, являются: • 🎱 трехмерные бильярды (C. Moore - Generalized shifts: unpredictability and undecidability in dynamical systems) • 🔦 3D оптические системы (J.H. Reif. J.D. Tygar, A. Yoshida - Computability and complexity of ray tracing) • 🧠 нейронные сети (H.T. Siegelmann, E.D. Sontag - On the computational power of neural nets) • ⚛️ спектральные щели в квантовой теории многих тел (T. Cubitt, D. Perez-Garcia, M. Wolf - Undecidability of the spectral gap) и т.д. А непосредственно тот же вопрос, что и посетил Тао - Способна ли гидродинамика к универсальным вычислениям? • T. Tao - Finite time blowup for an averaged three-dimensional Navier-Stokes equation • T. Tao - On the universality of potential well dynamics • T. Tao - Searching for singularities in the Navier-Stokes equations был задан ещё Муром в 1991 году: • C. Moore - Generalized shifts: unpredictability and undecidability in dynamical systems 🧮Анализ вычислительной сложности сегодня - один из базовых подходов в изучении физических систем. Она может включать в себя, например, неразрешимые явления универсальных вычислений или вычислительную сложность. Причём это важно не только с чисто теоретической точки зрения, но и с точки зрения разработки алгоритмов для определения долгосрочного поведения системы. Используя более физический язык - эта сложность часто отражается в существовании неразрешимых траекторий. Таких, что для вычислимых начальных условий, попытка определить, заведут ли эти траектории в некоторое заранее указанное открытое множество состояний фазового пространства, окажется неразрешимой или сколь угодно сложной с алгоритмической точки зрения. 💡Итак, если бы мы смогли построить жидкостный аналог универсальной машины Тьюринга, это позволило бы доказать неразрешимость некоторых явлений гидродинамики. То есть то, что иногда просто не существует алгоритма, гарантирующего, что частица жидкости пройдет через определенную область пространства за конечное время. 🐥Например, если мы отправим сообщение в бутылке, или потеряем в океане 29 000 резиновых утят (что произошло с грузовым судном во время шторма в 1992 году) - никто не сможет предсказать, где они окажутся. ⚠️ Но не путайте эту неразрешимость с хаосом. Создатели теоретической жидкостной универсальной машины - Ева Миранда и Даниэль Перальта-Салас (о них пойдёт речь в следующем посте) подчёркивают: - «В теории хаоса непредсказуемость связана с чрезвычайной чувствительностью системы к начальным условиям – взмах крыльев бабочки может породить торнадо. Но в данном случае дело идёт ещё дальше: мы доказываем, что не существует алгоритма, решающего задачу. Это ограничение не наших знаний, а самой математической логики.» 🚶‍♂️Ну а мы между тем, вплотную подошли к идее Тао. Остался еще один небольшой шажок.