Алгоритм, который переживёт тебя (The Halting Problem Paradox)

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

Но часто ли оправдано это ожидание, ведь многим из нас порой приходилось "отрубать" программу на полпути, перезагружать девайс, потому что по классике ВСЁ ЗАВИСЛО

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

И когда люди это осознали, они решили написать программу, которая будет анализировать поведение / программный код этих приложений и, как великий оракул, выдавать ответ на главные вопросы программистов: Запустится ли моя программа? Будет ли она работать? Соберётся ли она вообще? Сможет ли она выдать мне конечный результат или затупит на 99% загрузки? И назвали они эту группу вопросов "Проблемой остановки" или "The Halting Problem".

Справедливости ради, практически на все вопросы при определенных обстоятельствах наши оракулы - средства разработки (IDE) сегодня могут с успехом отвечать. Этот механизм называется статическим анализом, и он анализирует конкретно исходный код, как последовательность определенных лексем (выражений языка программирования), и при обнаружении явных нарушений он вызывает окно предупреждения или ошибки. Например, переменная, у которой нету стартового значения.

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

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

Но что, если мы даже не знаем, есть ли возможные варианты решения нашего алгоритма, что если он работает впустую. Может попасться задача, при которой остановка будет эквивалентна успешному завершению, но чтобы понять, будет ли эта остановка, нужно сначала знать, есть ли это решение. (Пример: найти нечетное совершенное число. Науке неизвестно есть ли оно или нет, а следовательно программа, которая будет заниматься перебором всех чисел, возможно будет выполняться бесконечно)

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

Представим, мы уже имеем такую машину. И две экспериментальные программы: калькулятор и шахматный робот.

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

Наша машина - анализатор получает на вход исходный код программы и входные данные для нее, а на выходе мы получаем ответ: (stuck / not stuck) заработает ли она или нет.

И эта машина работает тоже превосходно, она моментально отвечает на наши вопросы про остановку, какую машину бы мы ей не подали.

А теперь представьте себе, что есть программа, которая состоит из двух программ: нашей машины и программы, которая принимает 2 значения: stuck / not stuck, и инвертирует их

1. Если мы подали stuck, то машина не стопорится, а выдает ответ OK
2. Если мы подали not stuck, то машина стопорится.

Затем мы подаем исходный код в нашу главную машину. Как вы думаете, что она выдаст?

Рассмотрим опять, два варианта

1. Если машина выдала stuck, это значит что наша двойная программа застряла. Но она могла застрять только если в инвентор мы подали not stuck, а значит что НА САМОМ ДЕЛЕ программа не работала
2. Если машина выдала not stuck, это значит что инвертор выдал OK, но он смог бы это сделать, только если бы наш анализатор выдал бы STUCK, а это невозможно, как и случай 1.

Простым языком: наша программа НЕ СУЩЕСТВУЕТ, потому что

1. Она не смогла бы эмулировать сама себя бесконечное количество раз в реальном мире
2. Если бы она нарушила п.1, она бы выдала неразрешимую логическую ошибку
3. Не существует метрик для всех поведений программы => чисто логически такой код анализатора невозможно себе представить на текущий момент.

P.S. шутки ради, даже программа, которая будет на любой исходный код с любыми входными данными отвечать "not stuck" (print("not stuck") на питоне, к примеру), фактически она будет считаться анализатором с шансом правильного ответа 50/50.

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

Ставьте реакции, подписывайтесь на канал, обниму каждого из своих читателей лично (пишите в ЛС) 🥺🫡