Математические байки – Telegram
Математические байки
4.3K subscribers
1.44K photos
15 videos
27 files
914 links
Рассказы про разную математику.

Архив: http://dev.mccme.ru/~merzon/mirror/mathtabletalks/
Download Telegram
Внутри этих спиралей есть отталкивающая периодическая орбита периода 13 — с чуть большим 1 по модулю мультипликатором (производной за период):
| 0.9998485 - 0.0618222 i | = 1.001758
И, соответственно, спирали должны на неё наматываться (потому что множество Жюлиа инвариантно).
Для контроля — вот картинка, которую тут строит программа XaoS (спасибо Михаилу Раскину за наводку):
Математические байки
Photo
То есть — вот здесь, например, программа действительно делает недостаточно итераций, и под этим увеличением рисует заметно-неправильное множество.
И возникает вопрос: хорошо, а как определить, сколько ждать надо?
В этом месте должна бы начинать звучать драматическая музыка — потому что на слова "определить, сколько времени нужно ждать" одной из первых ассоциаций является алгоритмически неразрешимая проблема останова.
А именно — если мы рассматриваем компьютер (с бесконечной памятью; машину Тьюринга, чтобы формализовать слово "компьютер"), на котором будем запускать программы — то нет никакого универсального алгоритмического способа по любой программе правильно сказать, закончит ли она когда-нибудь работу, или нет.
То есть — есть очевидные случаи (скажем, если первой же командой идёт "закончить работу", или первым же делом программа сваливается в бесконечный цикл).
Есть менее очевидные, которые всё ещё можно обработать. Но нет никакого алгоритма, позволяющего правильно дать ответ во всех случаях.
Потому что — пусть такой алгоритм ( = программа) существует:
Испортим эту программу (которая должна была бы давать ответ всегда): пусть она зависает вместо того, чтобы печатать "OK" — но аккуратно печатает "FAIL":
А теперь запустим его самого на себе:
И получим классический парадокс лжеца: если он останавливается, то он должен был бы зависнуть из-за того, как мы его испортили (вместо того, чтобы напечатать "OK"), а если он зависает, то должен был бы добросовестно напечатать "FAIL" и остановиться.
(спасибо Анне Горденко за рисунки :) )
На самом деле — я тут чуть-чуть сжульничал: чтобы рассуждения выше стали совсем правдой, нужно сказать, что мы рассматриваем пару из программы и входных данных — а эти рассуждения доказывают алгоритмическую неразрешимость проблемы самоприменимости: "остановится ли программа, если её запустить на её собственном коде в качестве входных данных?"
Но если бы мы могли решать, остановится ли данная программа на данных начальных данных — то и про частный случай, "запустить на своём собственном коде", смогли бы ответить. А мы только что увидели, что даже для этого частного случая никакого алгоритма нет.
И это — теорема Алана Тьюринга 1936 года.