Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств

Владимир Игоревич Арнольд,
Математический институт им. В. А. Стеклова, Москва

От редакции

Перед вами два варианта лекции с одним и тем же названием.

Одна лекция — популярная, в том виде, в каком Владимир Игоревич Арнольд прочитал ее 13 мая 2006 года в концертном зале «Академический» по приглашению фонда «Династия». Эту лекцию, как уверяет сам академик Арнольд, может понять даже школьник.

Видеозапись лекции 13 мая: часть 1 (20 Мб), часть 2 (6,4 Мб), часть 3 (6,4 Мб).

Другая — для специалистов, написанная на строгом математическом языке. Она была прочитана 22 ноября 2005 года на заседании Московского математического общества.


37
Показать комментарии (37)
Свернуть комментарии (37)

  • vitar  | 30.05.2006 | 08:49 Ответить
    Уважаемые организаторы!

    А планируется ли опубликовать видеозаписи лекцмй 13 мая?
    Ответить
    • editor > vitar | 30.05.2006 | 16:25 Ответить
      Планируется, и уже довольно давно :-). Дело в том, что обработка видеозаписи и приведение ее к приемлемому для публикации в интернете размеру заняла у организаторов трансляции неожиданно много времени. Обещают к завтрашнему дню закончить.
      Ответить
      • gav > editor | 19.06.2006 | 21:30 Ответить
        А можно как-нибудь приобрести видеозапись в более хорошем качестве?
        Ответить
  • ringel  | 13.08.2006 | 19:27 Ответить
    А чем лучше проигрывать эти видеозаписи? Windows Media Player выдает ошибку
    Ответить
    • pterik > ringel | 15.08.2007 | 13:17 Ответить
      mov файлы - это "родной" формат для пакета QuickTime.
      http://www.apple.com/quicktime/
      Прямая ссылка на инсталятор:
      http://appldnld.apple.com.edgesuite.net/content.info.apple.com/QuickTime/061-2915.20070710.pO94c/QuickTimeInstaller.exe
      Ответить
  • irakly  | 17.09.2006 | 15:05 Ответить
    Все-таки логарифм - не самая сложная функция. Для p=17, n=2^4 логарифм L=11892 - многочлен 13-й степени, а не 16-й. Т.е., разности обращаются в нуль на 13-м шаге. Это даже вручную можно сосчитать (правда, я считал на компьютере).
    Ответить
    • Эд > irakly | 18.01.2007 | 19:51 Ответить
      А как насчет всех p mod4=3. Для всех таких простых p чисел меньших 100 логарифм не просто почти самая сложная сложная, а самая сложная.
      Я не смог найти опровергающего примера и при некоторых p>100 (хотя для исходной гипотезы Арнольда кроме p=17 есть еще 4 простых числа меньших 100, для которых она неверна). Неужели такие совпадения - случайность?
      Ответить
    • pterik > irakly | 15.08.2007 | 13:31 Ответить
      А по моему академик прав, и для этого не нужно брать в руки калькулятор.
      Для логарифмов, рассматриваемых в лекции, существует непрямая аналогия с "обычными" логарифмами, например с натуральными логарифмами.
      Производная любой порядка от натурального логарифма не обращается в константу. Как следствие, при стремлении к бесконечности логарифм растёт медленее, чем любая степенная функция. Наверное именно с этим фактом и связана сложность логарифмов.
      Ответить
  • irakly  | 17.09.2006 | 21:05 Ответить
    Как указано в статье, последовательности с нечетным числом единиц нельзя "проинтегрировать", т.е. они являются самыми сложными в своей компоненте связности. Пусть n=2^k, l=(1,0,0,0,0,0...) последовательность, в которой первый элемент 1, а остальные нули. Т.к. компонента связности всего одна, оказывается, что такая последовательноость будет "самой сложной". Даже случайная последовательность из 65536 знаков, из которых 32768 единиц, оказывается "проще". Кажется, это не очень соответствует интуитивному понятию сложности... Похоже, открытие Владимира Игоревича придется-таки закрыть. Впрочем, идея все равно интересная. Хочу еще посоревноваться с учениками В.И. и рассчитать структуру графа хотя бы до n=50. Может, обнаружится что-то интересное?
    Ответить
    • avmorkot > irakly | 26.12.2006 | 10:18 Ответить
      Определение сложности конечных последовательностей можно попытаться модифицировать. (Может быть, это уже кто-нибудь сделал?) Например, так.

      Пусть нужно узнать сложность последовательности a. В соответствии с определением В.И. Арнольда для каждой последовательности введем параметр s ("локальная сложность"), в пространстве последовательностей с метрикой r(x,y)=СУММА по i от 1 до n (модуль(x_i-y_i)) рассмотрим шар с центром в a и каким-нибудь радиусом (может быть, зависящим от n), усредним s по этому шару и то, что получится, назовем сложностью последовательности a.
      Ответить
  • grigus  | 01.02.2007 | 16:02 Ответить
    Оператор взятия разностей циклических слов можно рассматривать как клеточный автомат.Таким автоматам посвящены сайт и книга
    A New Kind of Science.
    Там должны быть графы и таблицы, подобные приведенным в докладе.
    Последние версии Mathematica позволяют проводить эксперименты с cellular automata.
    Ответить
  • relax  | 15.04.2007 | 22:48 Ответить
    Интересно отметить, как стоятся здесь графы: в одной и той же точке можно оказаться из нескольких точек, зато есть только один путь, которым можно уйти из определённой точки. Это напоминает то, как Пригожин поясняет необратимость времени в системах, стремящихся к равновесию: к одному и тому же исходу ведёт множество отличных друг от друга начальных условий.
    После просмотра доклада пришёл в голову аналог кубика Рубика:

    "Связные компоненты" графа этой штуки или циклические движения, можно получить вращениями вокруг перпендикуляров к трём плоскостям, отсекающим треугольники на каждой её грани, а "деревья" можно прилепить на место выпуклых пятиугольников с вершинами этой фигуры. А можно и соединить две такие штуковины, предварительно удалив у каждой по выпуклому пятиугольнику с вершиной, тогда получатся две связанные "связаные компоненты".
    Ответить
    • relax > relax | 15.04.2007 | 22:50 Ответить
      собственно штуковина:
      http://taip.nm.ru/Rubik.jpg
      Ответить
  • int  | 02.01.2008 | 02:28 Ответить
    Я хоть и не матеметик, а про логарифмы ничего не понял, пожет со второго раза пойму, т.к. по видео не очень понятно, но вообще очень интересно.
    Ответить
    • int > int | 02.01.2008 | 02:30 Ответить
      Попробую программу про перестановки написать, это элементпрно.

      Я считаю сложность ещё можно определять простотой сжатия информации, например вместо 1111111111111111111111 можно написать N единиц.

      Немного в сторону, например иногда номера телефонов пишут не 232 22 32 а
      232 2 232, но они не учитывают то, что не они одни такие и получается что нужно запоминать ещё и формат записи.
      Ответить
  • almir  | 23.02.2008 | 18:41 Ответить
    Уважаемый Владимир Игоревич!
    Я недавно познакомился с Вашим интервью "АКАДЕМИК В. И. АРНОЛЬД:ПУТЕШЕСТВИЕ В ХАОСЕ", выступлением в Государственной Думе и публичной лекцией.
    К моему большому удовольствию Ваши идеи о школьном обучении учащихся мне очень близки и понятны.
    Моё внимание, в частности, привлекли к себе Ваши две теоремы.
    Теорема 1. 'В каждой компоненте связности монады обязательно имеется цикл'.
    Доказательство. Множество точек конечное, поэтому, если мы выйдем и пойдём по стрелочкам, будем идти, идти, идти, когда-нибудь вернёмся в точку, где уже были раньше. Потому что их конечное число. Тогда от первого посещения этой точки до второго будет цикл. Конец доказательства.
    Математический цикл, о котором речь идёт в Вашей теореме и в её доказательстве, может быть описан, по-моему, значительно полнее и детальнее.
    Определённое время существования цикла в неопределённом пространстве подразделяется на 7 этапов: детство, юность, молодость, зрелость, старость, дряхлость и пора конца существования, смыкающегося с началом нового цикла. Шесть этапов (без последнего седьмого) цикла развития логического понятия были описаны Гегелем в малой 'Логике'. Три формы трёх этапов цикла (единичность, особенность, всеобщность) приходятся на развитие 'предварительного' понятия. Следующие три формы трёх этапов цикла (всеобщность, особенность, единичность) приходятся на развитие понятия как такового.
    Монада американского учёного-путешественника Уильяма Морриса Дэвиса (1850-1934) имеет форму закона развития рельефа Земли, названного им 'географическим циклом', который включает в себя шесть аналогичных форм без седьмой. Общие принципы идеального цикла Дэвис распространил на карстовый рельеф, пустынный рельеф, горноледниковый рельеф и рельеф морских берегов.
    Используя Вашу терминологию, могу сказать, что цикл, имеющийся в каждой компоненте связности монады, мною рассматривается в определённости цикла колебаний маятника часов с гирей, типа ходиков. Аналогичных примеров - не перечесть.
    Теорема 2. 'В компоненте связанности монады не может быть двух циклов'.
    Не стану цитировать Ваше доказательство теоремы, так как она привлекла к себе моё внимание не своим доказательством.
    Из неё, по-моему, можно сделать вывод о том, что 'В обязательных двух компонентах связанности монады обязательно имеются два цикла'.
    К двум циклам может иметь непосредственное отношение интерпретация Дирака к своей теореме спина электрона. Из его теоремы следует, что электрон-позитронная пара в качестве двух компонентов связанности монады имеют два значения.
    Дело в том, что электрон и позитрон, не изменяя своей внутренней энергии, взаимодействуют друг с другом и с внешней средой. Они поглощают рассеянную энергию внешней среды, изменяют её форму и обмениваются энергией внешней среды между собой Затем они вторично изменяют форму внешней среды и, наконец, излучают её в рассеянной форме во внешнёю среду.
    Аналогами монады Г. В. Лейбница и В. И. Арнольда могут быть правое и левое полушарие мозга человека, напольные самозаводящиеся часы в Амстердамском музее и другие. Всех - не перечесть.
    Таким образом, энергия внешней среды проходит через электрон-позитронную пару в двух прямо противоположных направлениях в виде двух различных по величине порций-квантов. Чтобы электрон-позитронная пара повернулась на 360 и вернулась в прежнее положение, её электрону и позитрону нужно, каждому в отдельности, повернуться на 720.
    С уважением, Миргородский Александр Илларионович.
    www.mirgorodsky.ru
    Ответить
  • edictum  | 29.09.2008 | 00:11 Ответить
    Может я ошибаюсь, но в году вроде 365, а не 364 дней, без високосного.
    Так что, похоже к астрономии это имеет весьма отдаленное отношение.
    Ответить
    • klein0 > edictum | 11.10.2008 | 05:31 Ответить
      Владимир Игоревич Арнольд: Я выписал и получил: компонент две. Оказывается, компонент две, они одинаковые. Имеется два одинаковых цикла, сумма длин которых 728. Трудный вопрос: какая длина каждого цикла? Какая длина каждого цикла? 728 надо разделить пополам. Значит, длина каждого цикла будет 728 пополам - равняется 364. А теперь мы, во-первых, обращаемся к астрономии. Мы получили длину года без високосного дня. А теперь мы обращаемся к моей теореме. Длина цикла делится на длину последовательности. А длина последовательности была 7. Значит, получаем вывод: 364 делится на 7. А теперь делим: 364 разделить на 7 - что получается? Ну, мои школьники умели. Сколько? 52 - число недель в году. А это равняется: 13 умножить на 4. Следовательно: 364 - год - состоит из 13 месяцев, лунных, по 28 дней в каждом. Что и требовалось доказать.

      edictum: Может я ошибаюсь, но в году вроде 365, а не 364 дней, без високосного. Так что, похоже к астрономии это имеет весьма отдаленное отношение.

      to edictum:

      - Да, ошибаетесь. :)) При создании "Земли + людей" не удалось замкнуть 3 цикла (слишком много параметров должно было быть сбалансировано, поэтому теория и практика немного различаются) - поэтому год 365, а не 364, у женщин месячные циклы, а человек должен спать.

      Чтобы, кстати, замаскировать последнее пришлось сделать, что и животные "спят" (им, поясняю, спать ни к чему, в отличие от человека). А чтобы замаскировать последнее последнее (что "им ни к чему, в отличие от человека") был создан сценарий их поведения при "депривации сна", отбивающий желание исследовать этот вопрос.

      Привет! :))
      Ответить
    • drusha15 > edictum | 25.09.2012 | 04:51 Ответить
      edictum, а когда и какого Петрика смущало несоответствие реальности (результатов наблюдений, опытов) его теории? Реальность в этом случае отметается, а теория возводится в догму. Рецепт прост.
      Ответить
  • Jammer  | 28.10.2008 | 11:52 Ответить
    Из статьи вынес только одно, математика - жестокая мозговая патология :)))
    Ответить
    • drusha15 > Jammer | 25.09.2012 | 04:59 Ответить
      Вы такой же вывод могли бы сделать про физику, послушав лекцию какого-нибудь Петрика. Однако, это не так. Так и здесь - не надо всех математиков под одну гребёнку. Среди них есть люди, совершающие великие прорывы, которые потом исследователи в других дисциплинах с успехом применяют. Не судите всех по одному.

      Кстати, может у него другие работы есть, более применимые. Эйнштейн тоже много в чём ошибался, однако ценим мы его не за его ошибки.
      Ответить
  • клетка  | 26.02.2009 | 20:29 Ответить
    Красив ученый , великая работа , но .... не все учел , а многое не знал . Что сразу не понравилось ? Монада . Неземное на земле не создать , но понять бы надо . Как живет дерево ? ПЕРИОДАМИ . А где они ? А как живет человечество ? Периодами . Неверна и бинарность у дерева - она прерогатива высших существ разумности особой - только их . В каждом из нас встроены эти самые бинары-труженики , ведущие отсчет нашего земного времени с отсчетом его в космическое наше время - вечное времене . Мы - вечны своим основным видом космических существ . Мы - не тела . Мы - в нем -урановоэнерговыстроенное .

    Могла бы добавить немного и о логарифмах и их состояниях во всем живом и во всей природе . А их антипод? Выяснили ли роль корня ? Там диво , что за роль . Людмила Белик
    Ответить
    • me123 > клетка | 15.01.2010 | 22:47 Ответить
      согласен с вами, клетка. о муравьях не подумал академик, а ведь мы муравьи, куда умнее клеток, мы даже по логарифмической линейке бегать можем взад и вперёд.
      Ответить
  • oxydan  | 04.06.2009 | 20:57 Ответить
    Ув. Владимир Игоревич!
    У меня не сходится с Вами случай n=12.
    Получается A^16=A^4, а не A^16=A^2
    Я воспользовался тем, что отображение A = x^2+x, которым Вы оперируете это линейный полином над простым полем характеристики 2 и оперировал с матрицей, которая представляет отображение A. Можно идти с другой стороны - по произвольной монаде построить полином над конечным полем, только степень полинома становится экспоненциально большой..
    Ответить
    • oxydan > oxydan | 07.06.2009 | 15:46 Ответить
      Виноват.. в Докладе в Московском математическом обществе такой ошибки нет..
      Ответить
  • Andrey_97  | 25.08.2009 | 02:10 Ответить
    Владимир Игоревич! Какую литературу Вы порекомендуете? Как относитесь к трудам, например, Акилова, Л.В. Канторовича?
    Ответить
  • velix  | 16.11.2009 | 03:23 Ответить
    Были приведены примеры "хорошо случайных" последовательностей (номера проезжающих автомобилей), но только вскользь упомянуты неслучайные.
    В частности, мне интересно, если дать человеку задание произнести вслух последовательность нулей и единиц (или что то еще сделать по возможности случайно и хаотично) будет ли это случайным в смысле, изложенным в лекции?
    Вдруг это будет косвенный метод определения мозговых отклонений? (типа того что нормальный человек выдает обычно неслучайные последовательности, больной - случайные)
    Ответить
  • me123  | 15.01.2010 | 22:40 Ответить
    самое замечательное в статье то, что никакого отношения к сложности ""сложность"-по арнольду" не имеет. а всё остальное, конечно, верно - переливание из пустого в порожнее. ха-ха-ха. хотя, некоторым детям, конечно сложно бывает...
    у меня тоже есть "me123-гипотеза": 0 сложнее 1.(или, наоборот).
    Ответить
    • drusha15 > me123 | 25.09.2012 | 04:46 Ответить
      - это у Вас аж две гипотезы - прямая и обратная. Можно учереждать премию тому, кто первым докажет. А Вы уже вошли в анналы истории математики, сформулировав эти гипотезы.
      Ответить
  • дядюшка Ро  | 16.12.2010 | 20:37 Ответить
    А, что будет если в степени числа поставить 3 миллиарда?.. Кстати, такое число фигурирует где-то в моих генах... Я бы хотел его найти на числовой оси, но нет оснований. Одни желания...(дядюшка Ро)
    Ответить
  • дядюшка Ро  | 17.12.2010 | 11:19 Ответить
    А я тоже так делал. Еще в школе... Интересно... Брал 10 миллиардов лет, переводил в секунды и извлекал корень кубического числа. Получал полмиллиона секунд. Как раз неделя, что в библии записана.
    Ответить
  • guryan  | 19.10.2011 | 19:17 Ответить
    Господи боже, теперь я понял, почему наука в глубоком кризисе. Вы же заменили физическую реальность математическими закорючками и пытаетесь высосать из нее какие-то истины. Математика - это даже не наука и нет в ней никаких истин. Это просто язык описания, и довольно примитивный. А языком можно описать и реальный предмет и написать фантастический рассказ. Я могу вам математически точно показать, что железный лом при нагреве до 1 миллиона градусов Цельсия, удлинится на 50 сантиметров. Ну и как это соотносится с реальностью? Утверждения ученых о падении материи самой на себя при гравитационном коллапсе, по степени идиотизма может конкурировать только с росказнями барона Мюнхгаузена о вытаскивании самого себя за волосы из болота. Природа намного проще,господа, чем вы тут напридумывали... не училась она никакой математике...
    Ответить
    • drusha15 > guryan | 25.09.2012 | 04:40 Ответить
      Не согласен только с тем, что математика "примитивный" язык описания. Язык как язык, местами даже очень сложный. Очень полезный, когда мы пытаемся количественные характеристики изучить.

      Но вот в таком применении, как в этой лекции... Хмм. Это "вычисление числа зверя" просто какое-то.
      Ответить
      • guryan > drusha15 | 22.10.2012 | 13:14 Ответить
        Математика полезна, когда нужно посчитать тугрики, площадь коттеджика или могилки. http://yadi.sk/d/MSViP5Jr01MAs
        Ответить
    • Мерзкая Бабайка > guryan | 25.11.2012 | 11:06 Ответить
      Математика - это действительно довольно "примитивный" язык описания, но лучшего ничего пока не придумано. Математика имеет дело с конструкциями априори, и именно по этому язык становиться сложен. А вообще в истории математики попеременно появлялись то "решатели" такие как Арнольд (Лежандр, Лопиталь, Кеплер, Колмогоров), и "обобщатели" - Галлилео, Лагранж, Гаусс. Поэтому здесь нет ничего сверхъестественного - это просто дальнейшее развитие науки.
      Ответить
  • drusha15  | 25.09.2012 | 04:31 Ответить
    Петрик просто отдыхает, а средневековые алхимики и астрологи с завистью кусают себе локти.

    Особенно понравился последний пассаж про нумерологию и длину года в днях. ;-)
    Ответить
  • роткив  | 16.07.2013 | 13:13 Ответить
    математику, как инструмент мне кажется не все достаточно полно понимают в её динамике развития по соответствию физических действий и построений в микромире,который в данной ситуатции для нас просто закрыт.а приложить к нему математику в данном классическом варианте, это опять же просто утонуть в прикладных комбинационных поисковых алгоритмах. в микромире на эти классические прилагаемые действия ответы разные.поэтому физика сейчас гуляющая,которая даёт вам лишь возможность в преобразовании летать только на горелках.не надо сейчас научной энтропии, надо переходить на другой уровень полной физической взаимосвязи с окружающим нас мире. ущербно для нас-да,улыбаться придётся по программе.без понимания самого элементарного действия-движения,не поймёте эволюционную строительную роль двух его сторон-то есть базовую парность в выявлении,в них показателей асимметрии.математику надо оживлять и уходить от классики механических машин.
    Ответить
Написать комментарий
Элементы

© 2005-2017 «Элементы»