Случайность, детерминированность и вычислимость
По понятным причинам сейчас резко возрос интерес к математическим моделям, графикам и предсказаниям. Об экспоненциальном росте рассуждают даже бабушки на скамейках. Но мало кто понимает что там скрывается глубоко под капотом. И это касается зачастую даже людей, которым неплохо было бы понимать, просто по роду их занятий.
Давайте попробуем разобраться насколько это возможно. Может в процессе я и сам что то пойму )
Три простых (казалось бы) понятия: случайность, детерминированность и вычислимость. Интуитивно мы вкладываем в эти слова вполне определённый смысл. Но интуиция здесь не очень работает.
Подбрасывание монетки — случайный процесс. Нет способа предсказать, что выпадет при следующем броске. Это может быть орёл или решка с шансами 50/50. Но если бросать монетку 1000 раз, то можно сделать вполне чёткие предсказания по поводу того сколько всего раз выпадет орёл, а сколько решка. Здесь много тонких моментов, например есть разница между “бросить одну монету миллион раз” или “бросить тысячу монет каждую по тысяче раз”, об этом будет отдельно, но суть остаётся. Несмотря на то, что процесс полностью случайный, мы можем довольно точно делать выводы о его будущем поведении.
Другой пример. Движение двух тел в пространстве, описываемое законами Ньютона. Теми самыми законами, что учат даже в школе. Это строго детерминированная задача и зная начальные условия, мы можем точно предсказать, что произойдёт даже через 1000 лет.
Добавляем ещё одно тело, теперь их три. И всё сразу же летит коту под хвост. Решения этой задачи в общем случае не существует в принципе. Есть довольно много частных решений, для конкретных условий, например если все тела на одной прямой, если образуют равносторонний треугольник и обладают одинаковой массой и т.д. Попытки решить эту задачу привели к появлению новой математической теории — теории хаоса (наверное многие слышали о ней в первой части Парка Юрского периода).
Если в двух словах, мы не можем решить эту задачу в общем случае. Можно попытаться решать задачу численно, по сути рассчитывая положение каждый раз заново через момент времени Δt. И вот тут начинается самое интересное. Малейшие изменения в начальных условиях приводят к тому, что уже через несколько десятков циклов результаты будет полностью отличаться. То есть мы возьмём какие то значения масс, скоростей и положений. Посчитаем всё на компьютере. Потом чуть-чуть поменяем хотя бы один из параметров. Посчитаем заново. На выходе будет… будет что то. Нельзя предсказать что именно. Решения уравнений внешне будут вести себя полностью как случайные процессы. Именно это, кстати, и называется “эффектом бабочки”. Бабочка махнула крылышками (минимальное изменение), а на другом конце земли начался ураган (непредсказуемость эффекта).
Неплохое видео (с переводом) как раз об этом.
Ещё раз. В первом случае у нас полностью случайный процесс. Но мы можем его предсказать и понимаем как он будет себя вести. Во втором процесс полностью детерминированный, более того, он описывается довольно простыми правилами. Предсказать ничего нельзя. Хаос.
Ещё один тонкий и важный момент. В расчётах мы используем действительные числа, которые мы умеем записывать только с каким то пределом точности + сами измерения имеют точность. Мы можем сказать, что масса этого шарика 8.874839484783…..47447 кг. Неважно сколько знаков после запятой мы запишем, всё равно их конечное количество. И вот то самое, что мы не записали будет иметь эффект на результат. Непредсказуемый.
Ситуация ещё хуже. Вычисления с действительными числами на компьютере не совсем точные, на каждом шаге происходит “срезка” до максимально возможной точности. Предположим мы посчитали нашу систему на миллион лет вперёд, а потом захотим посчитать ещё на год. Что бы не тратить время, мы не будем пересчитывать всё, а возьмём промежуточные результаты, скажем, за 800 тысяч лет и начнём с них. Результат для миллиона лет может полностью отличаться, от того, что было при первом расчёте. Причина — точность вычислений и хаотическое поведение системы. Строго говоря, этого может и не быть, зависит от железа на котором считаем и от софта. Просто теперь у нас система стало ещё сложнее. Три тела + компьютер.
А что если рассмотреть “идеальный компьютер” с полностью предсказуемым поведением?
Становится вопрос — “что такое идеальный компьютер”? Ответ дал Алан Тьюринг в 1936 году. Он разработал концепцию абстрактной машины и всё что делает эта машина предложил называть алгоритмом. По сути Тьюринг дал формальное определение тому, что мы понимаем интуитивно, когда записываем последовательность действий при решении какой-либо задачи. Кроме машины Тьюринга есть другие подходы: лямбда-исчисление, нормальные алгоритмы Маркова, но все они эквивалентны. Всё что можно сделать с помощью одного подхода, можно повторить другими. Все современные компьютеры тоже эквивалентны машине Тьюринга, то есть на них принципиально нельзя сделать ничего, что нельзя сделать и с помощью машины Тьюринга.
Машина Тьюринга — максимально простая штука и я не буду в точности описывать как она работает, есть масса материалов на эту тему. Кратко, для ясности.
Бесконечная лента, разбитая на ячейки. Головка которая может записать что то на ленту (определяют множество того, что может быть записано — это называется алфавитом). И есть “программа” — набор инструкций в стиле “если сейчас на ленте … то сдвинуть головку влево/вправо|записать что то поверх|остановиться”. Когда машина останавливается, то лента содержит конечный результат. Всё просто, но формально наши супер крутые компьютеры с гигабайтами программ и со всеми нейросетями не способны сделать ничего, что нельзя запрограммировать на машине Тьюринга.
Даже больше, есть такая штука как тезис Тьюринга-Черча, который гласит:
любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга
Согласитесь, это очень сильное утверждение.
Выше я написал, что одна из возможных команд для машины Тьюринга — это остановка. Но обязана ли она останавливаться? Совсем нет. Простейшая программа “сдвинуть головку влево, повторить” никогда не остановится (да, это не совсем валидная программа для машины Тьюринга, я упрощаю намеренно, это не меняет сути). Подвисающие приложение на компьютере прекрасно демонстрирует этот факт ).
Сейчас будет довольно таки сложный момент. Мы можем закодировать любую машину Тьюринга в число. Неважно каким способом.
Самое простое, я нумерую все возможные инструкции как 001, 002, …100, …
Я записываю программу (машину Тьюринга) просто как 121001012002… Очевидно, что так можно записать любую программу (только число будет длинным).
Вопрос. Могу ли я создать машину Тьюринга, которая выполняет другие машины Тьюринга? Принимает на вход число, описанное выше и выполняет программу. Да могу. Это будет называться универсальная машина Тьюринга. Любой компьютер это и есть универсальная машина Тьюринга.
А теперь главный вопрос. Могу ли я создать машину Тьюринга, которая сможет определять для любой другой машины Тьюринга, остановится та или нет? То есть на вход число/программа, а на выходе 0, если программа зависнет или 1, если она выдаст что то разумное.
Ответ парадоксальный и невероятно важный. Нет, такой машины Тьюринга не существует. Её не может быть в принципе и это можно (и даже не очень сложно) доказать.
Получается что есть целый класс задач, которые в принципе нельзя решить алгоритмически.
Многие смотрели Кремниевую долину. Там Ричард придумал очень крутой алгоритм сжатия данных, который умеет сжимать в сто раз лучше, чем все что были до этого, ну и с этого всё началось. Написание таких алгоритмов (имеющих огромную коммерческую ценность) напрямую связано с функцией “колмогоровской сложности”. И эта штука как раз невычислима. Это небольшая ремарка, что бы показать, что это вполне практические вещи.
Какие выводы?
Случайный — не значит “непредсказуемый”. Со случайностью вполне можно работать, она поддаётся оценке и вычислению.
Даже простые системы, описанные чётко определёнными правилами, могут демонстрировать полностью непредсказуемое поведение. Когда кто то рассказывает, что социальные и экономические процессы в мире прогнозируются и кем то управляются, мне смешно. Мы поведение трёх шариков в пустоте не умеем нормально рассчитывать. С другой стороны, если нами управляют рептилоиды, то всё понятно, их математика очевидно совершеннее нашей.
Но в теории мы умеем решать задачу трёх тел, ограничения вычислительные, не все системы ведут себя хаотично, есть масса частных случаев. Что то сделать можно… Но есть вещи, которые не поддаются алгоритмическому вычислению даже теоретически.
И это ещё не всё. По сути это только начало.