04.10.2018 18:26
Human2 35 1300 Источник
Продолжу начатую предыдущим постом тему доказательством гипотезы Коллатца.

В чём заключается эта гипотеза? Возьмём любое натуральное число $n$. Если оно чётное, то делим его на $2$, а если нечётное, то умножаем на $3$ и прибавляем $1$ (получаем $3n + 1$). Над полученным числом выполняем те же самые действия, и так далее. Гипотеза Коллатца заключается в том, что какое бы начальное число $n$ мы ни взяли, рано или поздно мы получим единицу.

Доказательство гипотезы Коллатца


Переформулируем гипотезу следующим образом: возьмём любое натуральное число $n$. Если оно чётное, то делим его на $2$ пока оно не потеряет свойство чётности, а потом переводим в систему счисления по основанию $\dfrac{1}{3}$ и прибавляем $1$ до тех пор, пока основание системы счисления не станет обратным $n$. Гипотеза Коллатца в такой формулировке заключается в том, что какое бы начальное число $n$ мы ни взяли, рано или поздно это произойдёт, то есть в том, что уравнение

$\dfrac{1}{pn}=\dfrac{1}{3^m+m}$

где $m$ — число нечётных шагов, $p$ — некое рациональное число с неизвестными свойствами, имеет решение при любом натуральном $n$, что очевидно так.

Доказано.

Но ничего не понятно, особенно почему я переформулировал гипотезу именно так.

Некоторые основные понятия теории энтропии


Система — неопределимое понятие, на основании которого строятся недоказуемые определения:
Энтропия — информационная ёмкость системы.
Экстропия — величина, противоположная энтропии.
Фазовый переход — уменьшение энтропии на один порядок, происходящий при накоплении достаточного и необходимого объёма знаний.

Эволюция маленькой n


Рассмотрим на конкретном примере: возьмём из формулировки гипотезы n и превратим его в $n$. Как этого достичь? Уменьшая незнание, то есть задавая вопросы на которые возможен только однозначный ответ «да» или «нет». Поехали:
1. n — самолёт? Нет. Этот ответ уменьшил наше незнание о n на знание «n — не самолёт», но не сообщил нам ничего о свойствах n, то есть он уменьшил энтропию, но не увеличил экстропию.
2. n — математический объект? Да. Этот ответ увеличил экстропию, теперь мы знаем, что n — математический объект, следовательно обладает всеми свойствами математического объекта, в частности является переменной либо константой.
3. n — константа? Нет. Этот ответ снова снизил энтропию и произвёл фазовый переход. Количество накопленной информации «n — математический объект» и «n — не константа» перешло в её качество — вывод "$n$ — переменная" и теперь позволяет нам уменьшить энтропию данных выше определений.

Энтропия (в математике) — неотъемлемое свойство математического объекта, мера нашего незнания о нём как о системе, величина измеряемая в битах энтропии. Неформально: ответ «нет» на вопрос.

Экстропия (в математике) — величина, противоположная энтропии (в математике), мера нашего знания о математическом объекте как о системе, величина измеряемая в битах экстропии. Неформально: ответ «да» на вопрос.

Фазовый переход (в математике) — уменьшение энтропии (в математике) на один бит энтропии, происходящий при накоплении достаточного и необходимого объёма знаний.

Немного магии теории энтропии


Так как же всё-таки я получил свой эквивалент гипотезы Коллатца? Допустим, что изначально $n$ имело вид $8m$, то есть содержало $3$ бита экстропии: ответы «да» на вопросы «делится ли $n$ на $2,4,8$ соответственно?» и некоторое количество бит энтропии, определяемое переменной $m$. Операцией деления на $2$ мы трижды экстропию понизили, в итоге она стала равна нолю, энтропия же осталась неизменной и равной $2^r$, где $r$ — число разрядов в двоичной записи числа $m$. Переводом в систему счисления с дробным основанием мы каждый раз совершали фазовый переход (в математике), так как получали знание "$m$ делится на $3$", то есть, выражаясь понятным программистам языком, совершали битовый сдвиг влево и заменяли ноль в крайнем правом разряде на единицу. В итоге за конечное число сдвигов у нас из полностью неопределённого числа получилось числа, все цифры в котором единицы, то есть число полностью определённое, энтропия которого равна нолю, запись которого в десятичной системе счисления $1$. Что и требовалось доказать.

Комментарии (35)


  1. yarric
    04.10.2018 22:54
    #19193757

    Ничего себе! А уравнения Навье-Стокса решите?


    1. Nikeware
      04.10.2018 23:06
      #19193785

      Доказательство в пару строк. Прям как с гипотезой Риманна ;-).


  1. ThisMan
    04.10.2018 23:27
    #19193859

    Вот интересно, откуда берутся такие гипотезы? Ну то есть, почему именно к нечетным нужно умножить на 3 и прибавить 1, а не два. Ведь можно таких последовательностей сколько угодно придумать и пытаться доказать. И есть какая то практическая зона применений?


    1. mihaild
      04.10.2018 23:53
      #19193919

      Если прибавлять не 1, а 2, то из нечетного получается большее нечетное, и ничего интересного не выйдет.
      Вообще есть обобщение: вместо разбиения на четные-нечетные, мы разбиваем на классы по модулю P, и для каждого класса делаем свое линейное преобразование (такое, чтобы результат для данного класса получился целым).
      Для такого обобщения можно доказать, что по заданным параметрам и начальному числу определить, дойдет ли последовательность до 1, алгоритмически нельзя.
      Соответственно, можно поменять параметры таким образом, что заведомо нельзя будет ни доказать, ни опровергнуть, что последовательность достигнет 1.

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


  1. mihaild
    04.10.2018 23:43
    #19193899
    +1

    Могу заметить, что понятие «система счисления по основанию 1/3» не определено, а прибавление числа не зависит от системы счисления.
    Кроме того, непосредственно проверяется, что 1 / (3 * 8) = 24, 1 / (3^3 + 3) = 1/30, 1/30 != 1/24. И еще 1 / (19 * 20) = 1 / 380, 1 / (3^7 + 7) = 1 / 2194, 1 / 380 != 1 / 2194. Так что наборы (n = 3, p = 8, m = 3) и (n = 19, p = 20, m = 7) не являются решениями уравнения 1/(pn) = 1 / (3^m + m).

    Еще можно заметить, что в последовательностях для чисел 12 и 13 одинаковое количество умножений и делений (по 2 умножения и 7 делений), так что любая попытка выразить исходное число через количество операций каждого вида обречена на провал.


    1. Human2 Автор
      05.10.2018 00:48
      #19194029

      Спасибо за конструктив, отредактировал. Что же касается понятия «система счисления по основанию 1/3», то оно не определено настолько же, насколько не определено понятие «система счисления по основанию 10»


      1. mihaild
        05.10.2018 00:57
        #19194049

        Определено. Система счисления по основанию 10 — это отображение множества натуральных (для простоты) чисел в множество строк в алфавите {0, 1, ..., 9}.

        Отредактировали замечательно — удалили единственную более-менее нормально сформулированную часть.
        С «неопределяемыми понятиями» есть проблема: гипотеза Коллатца формулируется как утверждение в, например, теории множеств. Соответственно любые используемые понятия должны быть определены в той же теории.
        (собственно даже в том, что у вас написано вместо определений, невооруженным взглядом видны противоречия, но копаться в этом смысла нет)


      1. Sirion
        05.10.2018 00:58
        #19194051

        Это не «конструктив». Если в доказательстве находят столь зияющие дыры, это не значит, что их нужно быстренько залатать и всё будет нормально. Это значит, что проблема глубже. В самой идее доказательства. И в самом понятии, что такое доказательство, в голове доказывающего.


  1. munrocket
    05.10.2018 00:55
    #19194043

    Что за система исчисления по основанию 1/3? Объясните на пальцах что вы доказываете, если вы пришли на ресурс для программистов. И чем вас традиционная система по основанию 3 не устроила, они же эквивалентны.


    1. mihaild
      05.10.2018 00:58
      #19194055

      Так вы не знаете, что такое система исчисления по основанию 1/3 (я точно не знаю), или знаете, что она эквивалентна системе с основанием 3?)


      1. munrocket
        05.10.2018 01:03
        #19194073

        Автор не умеет излагать свои мысли просто, а делает `короткое доказательство`, поэтому под этой фразой могло быть что угодно. Очевидно число Пи в системе исчисления 1/10 будет бесконечно «большое» и записываться так ...5141.3 и в чем профит спрашивается?


        1. Welran
          05.10.2018 13:44
          #19196307
          +1

          Эмм, кому это очевидно?


    1. PastorGL
      05.10.2018 01:15
      #19194093

      Основанием системы счисления может быть что угодно, кроме нуля. Не обязательно целое, и даже не обязательно рациональное число, примеры см. в Википедии.


      1. munrocket
        05.10.2018 01:19
        #19194095

        Тогда он умышленно усложняет свое доказательство. Так как большие цифры не удобно в системе 1/3 записывать. C таким же успехом можно было выбрать основание 3.


  1. staticlab
    05.10.2018 01:01
    #19194063

    все цифры в котором единицы… запись которого в десятичной системе счисления 1

    В любой системе счисления с натуральным основанием существует бесконечно много чисел, которые записываются исключительно цифрами 1, но только одно из них равно 1.


  1. gecube
    05.10.2018 01:54
    #19194133

    В чём заключается эта гипотеза? Возьмём любое натуральное число. Если оно чётное, то делим его на, а если нечётное, то умножаем на и прибавляем (получаем ). Над полученным числом выполняем те же самые действия, и так далее. Гипотеза Коллатца заключается в том, что какое бы начальное число мы ни взяли, рано или поздно мы получим единицу.

    Не понял. Зачем умножать на 3? С тем же успехом можно было взять гипотезу, что:
    — берем четное число и делим его на 2;
    — берем нечетное число и добавляем к нему 1;
    Рано или поздно придем к 1.


    1. mihaild
      05.10.2018 01:58
      #19194143

      Затем, что гипотеза Коллатца формулируется так. Можно рассмотреть и другие правила преобразования. Для некоторых из них (например, «делить четные на 2, прибавлять к нечетным 1») задача получится тривиальной. Для некоторых — заведомо неразрешимой (не получится ни доказать, ни опровергнуть, что рано или поздно придем к 1).


      1. gecube
        05.10.2018 01:59
        #19194145

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


        1. mihaild
          05.10.2018 02:22
          #19194175

          Что значит «с другими значениями n»?
          Обобщение последовательности выглядит так: выбран модуль P, и дан набор правил вида «если x дает остаток i по модулю P, то заменяем x на a_i x + b_i». Начинаем с какого-то числа. Придем к 1 или нет?

          Гипотеза Коллатца: для P = 2 и правил «четное делим на 2», «нечетное умножаем на 3 и прибавляем 1» и любого первого члена рано или поздно придем к 1.

          Ничего особо фундаментального именно в этом наборе правил вроде бы нет. Просто «по историческим причинам» рассматривается именно он.

          >Можете в общем случае доказать для любого n, что либо существует доказательство для сходимости этого «ряда» к определенному числу, либо нет?
          Да, я могу доказать, что для любого конкретного утверждения либо существует его доказательство, либо не существует:) Вы, видимо, хотели спросить что-то другое.


          1. Hardcoin
            05.10.2018 08:56
            #19194709

            Да, я могу доказать, что для любого конкретного утверждения либо существует его доказательство, либо не существует:)

            Интересное утверждение. На самом деле можете? Это вообще возможно?


            1. mihaild
              05.10.2018 14:50
              #19196759

              Да, элементарно.
              Пусть X — наше утверждение.
              Формула «А или не-А» является тавтологией исчисления высказываний.
              Подставляем вместо A утверждение «X доказуемо». Получаем что "(X доказуемо) или (X недоказуемо)" является логической аксиомой исчисления предикатов.
              Соответственно, последовательность
              1. (X доказуемо) или (X недоказуемо)
              является доказательством утверждения в исчислении предикатов.


              1. Hardcoin
                05.10.2018 14:55
                #19196797

                В таком виде да. Я сначала, что вы можете доказать доказуемость/недоказуемость. А то, что верно одно из двух (но мы не знаем, какое) — это и так понятно )


                1. mihaild
                  05.10.2018 15:17
                  #19196923

                  Ну вы спрашивали
                  >Можете в общем случае доказать для любого n, что либо существует доказательство для сходимости этого «ряда» к определенному числу, либо нет?
                  Прочитать это синонимично к «по n проверить, доказуемо ли утверждение», я не могу.

                  Т.к. к задаче «верно ли, что для данного набора правил последовательность, начинающаяся с данного числа, придет к 1» сводится проблема останова, то понятно, что для любой (хорошей) теории есть набор правил и начальный член, такие что в этой теории нельзя ни доказать, ни опровергнуть наличие единицы в получающейся последовательности нельзя.
                  Для некоторых конкретных наборов правил и начальных членов можно легко.
                  Что получается при наборе правил из гипотезы Коллатца — не знаю, и никто не знает.
                  Если гипотеза Коллатца верна, то для любого конкретного n можно доказать, что начинающаяся с него последовательность придет к 1. Если неверна — может в принципе оказаться, что для какого-то n нельзя ни доказать, ни опровергнуть что начав с него придем к 1.


  1. Refridgerator
    05.10.2018 05:25
    #19194413

    Ждём простое доказательство теоремы Ферма через магию теории энтропии.


    1. staticlab
      05.10.2018 08:41
      #19194663

      В прошлой серии автор написал доказательство гипотезы Била через энтропию. Великая теорема Ферма легко доказывается при условии справедливости этой гипотезы. Доказательство приведено здесь.


      1. Refridgerator
        05.10.2018 09:43
        #19194869

        Да, действительно, брать надо выше — искать простое доказательство abc-гипотезы, ведь Мотидзуки с ним явно что-то намудрил.


        1. Sychuan
          05.10.2018 18:55
          #19198053

          Вроде как у него уже нашли ошибку www.quantamagazine.org/titans-of-mathematics-clash-over-epic-proof-of-abc-conjecture-20180920
          И судя по блогам математиков для Мотидзуки все очень плохо.


  1. Temmokan
    05.10.2018 08:19
    #19194615

    Доказательство, я так понимаю — это фраза «что очевидно».

    Что-то мировое математическое сообщество ни единым словом не выразило ликования по поводу решения гипотезы.


    1. Sirion
      05.10.2018 10:56
      #19195191
      +1

      Зато на хабре уже 9 плюсов. Мне было бы очень интересно пообщаться с их авторами.


      1. staticlab
        05.10.2018 11:40
        #19195477

        Если точнее, к этой статье было 13 плюсов, а к предыдущей 18.


        1. Sirion
          05.10.2018 11:46
          #19195515

          Мне интересно, эти люди вообще читали текст, или плюсанули не глядя, потому что «огого математика хабр торт!1»


      1. mihaild
        05.10.2018 15:25
        #19196959

        Приходите в дискуссионный раздел dxdy или на вихру (если еще не), там таких много.


        1. Sirion
          05.10.2018 15:36
          #19197019

          Ну, я думал, тамошние обитатели там и живут, не выбираясь массово на другие ресурсы.


      1. Refridgerator
        05.10.2018 18:28
        #19197941

        Зато на хабре уже 9 плюсов. Мне было бы очень интересно пообщаться с их авторами.
        Ну, я поставил прошлой статье плюс. Объясню, почему:

        1) мне самому недавно наставили минусов, хотелось реабилитироваться и поддержать плюсом другого несчастного;
        2) тема интересная, и к оформлению статьи нет претензий;
        3) даже если автор ошибается — все иногда ошибаются, это как минимум даёт повод для дискуссий;
        4) жанр «математическая фантастика» тоже имеет право на существование.


        1. mihaild
          05.10.2018 19:02
          #19198079

          Это не ошибка, это not even wrong. И даже если человек по какой-то причине никогда не слышал про то, что используемые понятия нужно определять — в комментариях ему про это сказали, но улучшений не произошло.