И получим классический парадокс лжеца: если он останавливается, то он должен был бы зависнуть из-за того, как мы его испортили (вместо того, чтобы напечатать "OK"), а если он зависает, то должен был бы добросовестно напечатать "FAIL" и остановиться.

(спасибо Анне Горденко за рисунки :) )

На самом деле — я тут чуть-чуть сжульничал: чтобы рассуждения выше стали совсем правдой, нужно сказать, что мы рассматриваем пару из программы и входных данных — а эти рассуждения доказывают алгоритмическую неразрешимость проблемы самоприменимости: "остановится ли программа, если её запустить на её собственном коде в качестве входных данных?"

Но если бы мы могли решать, остановится ли данная программа на данных начальных данных — то и про частный случай, "запустить на своём собственном коде", смогли бы ответить. А мы только что увидели, что даже для этого частного случая никакого алгоритма нет.

И это — теорема Алана Тьюринга 1936 года.

Так вот — есть метод, который позволяет иногда ответить на вопрос, останавливается ли программа: скажем, подождать годик, вдруг остановится. И кстати — это не такой дурацкий способ!
Я приведу цитату из (очень живым языком написанной) статьи А. Разборова в сборнике "Студенческих чтений НМУ", https://www.mccme.ru/free-books/globus/iumlectures1.pdf , которую (как и весь сборник — и последовавшие за ним выпуски "Глобуса") очень советую:

Но проблема этого метода — всегда остаётся сомнение, а достаточно ли мы подождали?

Так вот — теперь, и при взгляде на множество Жюлиа и его построение ("подождать достаточно долго"), должно закрасться то же подозрение. Так вот — закрадывается оно по делу — и я тут процитирую статью Бравермана и Ямпольского (https://arxiv.org/pdf/math/0610340.pdf ) :

То есть — заполненное множество Жюлиа построить можно (что уже неочевидно). Но вот для настоящего множества Жюлиа — для границы заполненного — это уже неправда!
Есть такие c, которые можно "указать явно" (точнее, написать программу, задающую их со сколь угодно высокой точностью) — что никакой алгоритм не сможет сколь угодно точно это множество нарисовать.

Про ренормализацию и константу Фейгенбаума я расскажу в следующий раз; а пока порекламирую видео Veritasium
https://www.youtube.com/watch?v=ovJcsL7vyrk —
и Numberphile
https://www.youtube.com/watch?v=FFftmWSzgmk +
https://www.youtube.com/watch?v=NGMRB4O922I +
https://www.youtube.com/watch?v=4LQvjSf6SSw
И на этом на сегодня я завершаю дозволенные речи.

поздравляем Сергея Константиновича Ландо с 65-летием!

завтра (10.07) — конференция, https://math.hse.ru/announcements/376454323.html

https://mccme.ru/free-books/lando/lando-genfunc.pdf

напомним также про небольшую книгу С.К.Ландо про производящие функции

«Предметом нашего исследования будут задачи перечислительной комбинаторики. Они заключаются в подсчете числа объектов, принадлежащих некоторому семейству конечных множеств. (…)

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

Определить, что такое хорошее решение, довольно трудно. Зачастую можно лишь сравнить два решения и сказать, какое из них лучше.

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

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

«Мне хотелось написать простую и доступную книгу, уделив внимание в первую очередь ярким примерам, а не общим теориям (которые, к тому же, зачастую отсутствуют). (…) Предлагаемая вниманию читателей книга написана на основе специального курса, читавшегося студентам Независимого московского университета в 1992–99 гг.»

«Лекции о производящих функциях» легли в основу и более подробной книги «Введение в дискретную математику», https://biblio.mccme.ru/node/2720/ (соответствующей уже курсам на матфаке ВШЭ)

И — я в дополнение ещё порекламирую книгу Ландо-Звонкина "Графы на поверхностях":
https://www.rfbr.ru/rffi/ru/books/o_26646

Слайд из идущего сейчас доклада Д. Звонкина:

Немного оффтопик, но может быть, не все ещё видели, что на небе сейчас есть яркая комета — Neowise.
Я вот в своё время не посмотрел на комету Хейла-Боппа (https://ru.wikipedia.org/wiki/C/1995_O1_(%D0%A5%D0%B5%D0%B9%D0%BB%D0%B0_%E2%80%94_%D0%91%D0%BE%D0%BF%D0%BF%D0%B0) ) — не знаю, почему, но узнал о том, что она была, только много лет спустя, а тогда "прощёлкал клювом".

Сейчас на небе можно увидеть комету невооруженным глазом. Лично я до сих пор еще не видела кометы без бинокля или телескопа. Красивое и редкое событие!

Комету Neowise сейчас особенно здорово наблюдать тем, кто живет южнее 60 широты. В Питере пока слишком светло и я, например, не смогла увидеть комету прошлой ночью, наблюдая за облаками.

Коротко: комету лучше наблюдать около полуночи, ниже и левее, чем звезда Капелла. В ближайшие дни можно продлить прямую Капелла – Менкалинан (Бета Возничего) и отложить за Менкалинан такой же отрезок.

Мне понравились обновляемые ежедневно поисковые карты на этом ресурсе: https://theskylive.com/c2020f3-info
Кроме того, здесь же опубликованы полезные ссылки на информацию о комете. Правда, все на английском.

Прикрепляю картинку для поиска отсюда: https://skyandtelescope.org/astronomy-news/anticipation-grows-for-comets-neowise-and-lemmon/

На русском есть отличный FAQ от AstroAlert: https://vk.com/astro.nomy?w=wall-727032_224245