Как стать автором
Поиск
Написать публикацию
Обновить

Комментарии 39

Не понял, каким образом задача Танежи вдруг стала фундаментальной, если она использует «конкатенацию» цифр, которые зависят от системы счисления?
Всего голосов 5: ↑5 и ↓0 +5
Она и не стала. Перечитайте статью. Речь идёт о новом математическом аппарате и связанном с ним подходе к решению переборных задач на ПК — подходе, без которого вывод для числа 10958 нереально построить. Фундаментальность самой задачи Танежи нигде не утверждается. Цитата из заключения:
Сама задача Танежи обнажает проблему полного дискретного представления и показывает несостоятельность популярных методов описания структуры данных при решении математических задач на ПК
Комментарий пока не оценивали 0
там абзац этому посвятили:
Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача. Так было с формальным обоснованием невозможности построения квадратуры круга циркулем и линейкой, с малой проблемой Гольдбаха и рядом других математических проблем. Так происходит и сегодня. Постановка задачи о представлении натуральных чисел при помощи семи операций над некоторым начальным вектором, подарила миру не только красивые частные решения и загадочную константу 10958, но и особый подход к классификации величин, значения которых не всегда могут быть записаны в явном виде. Так, доказано, что радикальные числа имеют ненулевое пересечение с множеством алгебраических чисел, но не входят в последнее полностью.
Комментарий пока не оценивали 0
Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача.

При аналитическом подходе к решению задачи Танежи в восходящем порядке естественным образом возникает понятие конечно-трансцендентного числа. И за это мы благодарны Индеру Танеже. Но сам он никакой классификацией трансцендентных действительных величин не занимался. Об этом идёт речь. Мы ценим не саму возможность представления целых при помощи замыкания над множеством чисел от 1 до 9, а ту математическую теорию, которая благодаря изучению этой возможности возникает.
Комментарий пока не оценивали 0

Пожалуйста, уберите длинные простыни кода и вывода под кат. Мотивация дочитать до конца и понять сильно повысится.

Всего голосов 2: ↑2 и ↓0 +2
Поправил :)
Всего голосов 2: ↑2 и ↓0 +2
Спасибо!
Всего голосов 2: ↑2 и ↓0 +2
НЛО прилетело и опубликовало эту надпись здесь

Кончились задачи, которые можно решить в одиночку, не будучи супергением.
FTFY.

Комментарий пока не оценивали 0

Нерешённых (вопрос, считать ли их все актуальными?) проблем в математике — море: https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics.


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

Комментарий пока не оценивали 0
Проблема в том, что некоторые люди не осознают как сильно решение «практически полезных» задач той же физики зависит от математического аппарата. Без производных не были бы запущены на орбиту спутники, которые обеспечивают беспроводной интернет вам и позволяют написать этот комментарий. Поверьте, сотни компаний — производственников сегодня ждут решения открытых математических проблем. И если для вас связь между «составлением из цифр» и выходом нового поколения электроники не очевидна — это говорит лишь о недостатке образования. Пишу искренне, не желая никого обидеть. Спасибо!
Всего голосов 1: ↑1 и ↓0 +1
НЛО прилетело и опубликовало эту надпись здесь

В чём физический смысл теоремы Ферма или диофантовых уравнений? Наверное, ни в чём, но при решении связанных с ними задач была придумано масса методов, были найдены неожиданные связи между геометрией и алгеброй и т.д… Попытки оценить плотность простых чисел внесли вклад в развитие комплексного анализа, были получены многочисленные тождества для всяких спецфункций, которые через пару сотен лет неожиданным образом оказались нужны для физики.


В общем, синтетические задачи — это не обязательно плохо. Часто они являются драйвером развития общих математических методов.

Всего голосов 2: ↑2 и ↓0 +2
*10958
Есть такое замечательное понятие: Гильбертова интуиция. Оно поможет вам понять, что происходит.
Давид Гильберт — немецкий математик XIX-XX веков. На втором международном математическом конгрессе 1900 года он предложил 23 «фундаментальные» задачи современной (ему) математики и обосновал их значимость весьма оригинальным образом.
Рассмотрим поведение профессионального математика при решении некоторой задачи. На первом этапе решения математик пытается получить наиболее простую (так называемую «рабочую версию») формулировку задачи. Речь не всегда идёт о простоте в научно-популярном смысле, как это происходит сейчас с проблемой Гольдбаха-Виноградова и проблемой Эрдеша. Математик ищет простую для себя формулировку. Так не секрет, что без ограничения общности некоторой геометрической задаче можно поставить в соответствие алгебраическую модель. А задачу из теории чисел, наоборот решать в топологиях. И если наш герой более компетентен в геометрии, он будет искать наиболее понятную геометрическую трактовку для большинства задач, вне зависимости от раздела-источника задачи.
На втором этапе происходит процесс «эвристического поиска уязвимостей». Решая однотипные задачи математик не развивается — такие упражнения полезны при подготовке к ЕГЭ, выступлении на олимпиадах — не более. Но рассматривая задачи с принципиально разным подходом к решению, относящиеся к некоторой узко специальной области, ученый формирует ряд ложных корреляций, которые составляют математическую интуицию. Так, имея на начальном этапе несколько путей анализа задачи, математик с опытом может «наугад» выбрать тот путь, который с большей вероятностью приведёт к стройному решению.
Наряду с интуицией отдельного математика, Гильберт рассматривает коллективное «ощущение важности» некоторых задач для всего математического сообщества. Так, диофантово уравнение ${a^n}+{b^n}={c^n}$ уже на тот момент не являлось единственным нерешаемым неопределённым уравнением в целых числах, однако «математическое чутьё» подсказывало, что при решении именно этого уравнения возникнет необычайно ценный математический аппарат, который будет применяться в различных областях науки.
Гильбертова интуиция — это способность отобрать из числа бесполезных задач как таковых (ибо нахождение корней для уравнения ${a^n}+{b^n}={c^n}$ не несёт ничего полезного) — те, с решением которых престиж математики, возможности теоретического аппарата и уровень влияния на другие науки возрастут.
Задача Танежи как таковая не несёт пользы, но для её решения (как оказалось при детальном рассмотрении, результаты которого частично приведены в этой статье) потребуется развить трансцендентологию и расширить современную дискретную математику теорией ПДП. То, как сильно современные астрофизика, нейробиология и ряд других прикладных дисциплин зависят от дискретки думаю пояснять не требуется.
Комментарий пока не оценивали 0
По поводу связи с представлением в целых числах можно еще вспомнить степени i.
i это поворот вектора на π/2 через комплексное направление, поэтому i2 это поворот на π, что эквивалентно умножению на -1.
i1/2 это поворот на π/4, а его проекции на координатные оси равны √2/2 = (1/2)1/2.
Всего голосов 1: ↑1 и ↓0 +1
Для задач, при решении которых приходится выполнять операции с комплексными алгебраическими числами и некоторыми трансцендентными, являющимися линейной комбинацией алгебраических чисел и числа $\pi$, тип данных Complex как структуру можно считать ПДП минимальным для некоторых из таких задач.
$i^{1/2}$ это поворот на ${\pi}/4$, а его проекции на координатные оси равны ${\sqrt {2}}/2 = {(1/2)}^{1/2}$.

Интересная идея! Действительно, некоторые комплексные величины, целая и мнимая часть которых являются целыми числами, либо для которых существует тригонометрическая форма записи с рациональными углами (в градусном их измерении), в точности представляют такие иррациональные значения, как ${\sqrt {2}}/2$ и позволяют выполнять некоторые операции над этими значениями без погрешности.
Комментарий пока не оценивали 0

Гауссовы целые (и рациональные) числа?

Всего голосов 1: ↑1 и ↓0 +1
Точно!
Комментарий пока не оценивали 0
Интересно, это как нибудь связано с мерой рациональности числа?
Также, мне кажется тема «нормальных» чисел более фундаментальна
Всего голосов 1: ↑1 и ↓0 +1
Интересно, это как нибудь связано с мерой рациональности числа?

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

Для математики — да. Для прикладной информатики — тема «конечно-трансцендентных» сегодня важнее. К тому же, в работах математиков 2010-2020 годов слишком часто стали появляться высказывания о «беспомощности» современной алгебры при работе с трансцендентными величинами. Пока даже доказательство факта трансцендентности является нерешаемой задачей для большинства классов действительных величин. Например: трансцендентность десятичных логарифмов целых, отличных от степени десятки, чисел была доказана, однако вопрос о трансцендентности логарифма числа, взаимно простого с основанием этого логарифма является открытой математической проблемой, не уступающей по «безнадёжности» ABC-гипотезе.
Комментарий пока не оценивали 0

Кстати, Вы не задумывались о том, что получение произвольного числа из вектора 123456789 и ограниченного набора операций близко к проблеме Collatz в ее инверсной форме: от 1 и двигаясь "назад" получить любое целое?

Всего голосов 1: ↑1 и ↓0 +1
Спасибо! Проблема Коллатца:

Всё зависит от того, как вы определяете понятие близости для двух математических проблем))
Задача Танежи как таковая проще проблемы Коллатца хотя бы потому, что требует разложения с использованием конкретного количества бинарных операций (а именно 8-и). Если же думать о Collatz как о сужении понятия конечной-трансцендентности для некоторого числа как принадлежность этого числа замыканию $\overline{\rm M}$ единичного множества $M$ относительно унарных операций ${op}_1 (n) = 2*n, {op}_2 (n)=\{{(n-1)}/3, n \equiv 1 (mod 3); {(n+1)}/3, n \equiv 2 (mod 3) \}$, то можно как минимум показать что всякому элемента из множества $N$ (натуральных чисел) можно сопоставить элемент множества $\overline{\rm M}$, но такое соответствие не обязательно является взаимно-однозначным. Пример:
Возьмем натуральное число 12. Запишем его в двоичной системе исчисления: $12_{10} = 1100_2$. Тогда длину двоичной записи, уменьшенную на единицу (3) будем интерпретировать как количество операций, используемых при выводе соответствующего элемента из $\overline{\rm M}$, а вектор $(0, 0, 1)$ цифр двоичного представления, записанных в обратном порядке без старшей цифры — как номера соответствующих операторов. Тогда для любого натурального числа количество операций может быть однозначно интерпретировано как длина единственного возможного двоичного представления и любой набор операций представим соответствующим натуральным числом (запись в обратном порядке и удаление старшей цифры были необходимы для того, чтобы такие выводы, как: $(0, 0, 0)$ и $(0, 0)$ были представимы и различимы). Так число 12 производит элемент: $(1*2*2-1)/3=1$
Дальнейшие перспективы решения проблемы Коллатца туманны. Так из факта существования ПДП для задачи Танежи следует её алгоритмическая разрешимость, в то время как для задачи Коллатца доказана её неразрешимость на некотором полном по Тьюрингу языке программирования (а именно, Fractran).
Комментарий пока не оценивали 0
О Mad Astronomer говорится в статье, но само видео от них не прикреплял. Спасибо!
Комментарий пока не оценивали 0
В теории — прикольно
На практике — хранение неупакованных данных в памяти дешевле, чем затраты процессора на перепаковку
МБ для каких-то супер-пупер компьютеров это не так, там проц дешевле оперативы и тогда это будет иметь смысл. Но что-то я сомневаюсь в таких суперкомпьютерах
Комментарий пока не оценивали 0
Речь не всегда идёт о перепаковке данных с целью уменьшения сложности по памяти. Для некоторых задач реализация алгоритма решения с типом double будет некоректна из-за громадных погрешностей. И когда вам нужно проверить равенство значения функции в точке некоторой константе, а на выходе получаете: $f({x_0}) = 2 \pm 1000 $, тогда приходится описывать сложную структуру данных, чтобы минимизировать погрешность или вовсе организовать работу с точными численными значениями величин, непредставимых конечной или бесконечной периодической десятичной дробью. В таких ситуациях ПДП (полное дискретное представление) — важный ориентир для программиста.
Комментарий пока не оценивали 0
Почему бы не написать алгоритм, который переберёт все возможные решения. Вариантов ведь не так и много…
Комментарий пока не оценивали 0
Потому что в int, double, Complex и даже BigInteger он не переберёт…
В статье дан ответ на этот вопрос. Если коротко и на примерах, то с такими числами как $ 2^{({3^4}^5)} $ и $6^{7^{89}}$ работать на компьютере проблематично, а в теории то что $ {2^{({3^4}^5)}} /{6^{7^{89}}} \neq 10958$ — неочевидно и требует строгой проверки. И такие варианты, с которыми нельзя справится даже на суперкомпьютерах — составляют порядка 15% от общего числа выводов. Помимо этого, работа с иррациональными числами на компьютере как правило ограничена работой с их вещественным приближением. И для некоторого выражения: $\sqrt {{\alpha}+{\beta}^{\sqrt {\gamma}}}$ на компьютере можно получить лишь приближение: $\sqrt {{\alpha}+{\beta}^{\sqrt {\gamma}}} = 10958 \pm {10}^{20}$. Отсюда вытекает проблема полного дискретного представления для иррациональных и трансцендентных величин.
Комментарий пока не оценивали 0
Поправьте пожалуйста в примерах:
(1+2^3)*4-5=(1+8)*4-5=9*4-5=36-5=31,
а не 35, как у Вас написано.

PS: по-моему, никто еще не отметил эту ошибку
см. Точная формулировка и первые обобщения
Всего голосов 1: ↑1 и ↓0 +1
Спасибо, исправил!
Комментарий пока не оценивали 0
Забавно, а я давал задачку на поиск разложения 10958 студентам в качестве практики по программированию. Понятно, что не фундаментальное исследование, а просто перебор всех возможных вариантов, забив на сверхбольшие числа и всевозможные неточности double. А тут из этой задачи современную проблему математики создают.
Мне казалось, что отсутствие разложения уже доказано, ведь несложно показать, что среди лесенок из степеней этого числа нет, а всё остальное перебирается в лоб.
Всего голосов 1: ↑0 и ↓1 -1
Тем не менее, по состоянию на 1 июня 2020 ни одно из предложенных «полных» решений задачи Танежи не прошло проверки. Задача открыта.
Всего голосов 1: ↑1 и ↓0 +1
Интересно. Полезность задачки для студентов это не уменьшает, а интереса добавляет. Признаю, зря я был так категоричен в «несложно показать».
Всего голосов 1: ↑1 и ↓0 +1

Но ведь при наличии среди допустимых операций вычитания и деления перебором задача так просто уже не решается...

Всего голосов 1: ↑1 и ↓0 +1
А чем мешает вычитание? Деление имеет проблемы с точностью, это я понимаю, но что с вычитанием не так?
Комментарий пока не оценивали 0

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

Комментарий пока не оценивали 0
Вы имеете в виду врехнюю границу промежуточного результата? А зачем? Отсекать количество вариантов тут не надо, вариантов не так много, чтобы не перебрать все. Можно ли доказать, что среди экстремально больших промежуточных результатов не может быть искомого? Мне кажется, что можно, не так много действий могут приводить к чему-то большому.
Полный перебор (забив на все переполнения и неточности, поэтому и не полностью корректный как доказательство) в даблах на домашнем компе у меня занял 40 секунд. Длинная арифметика сразу увеличивает время в разы (что ерунда для глобальной задачи), но от точности и непредставимости результатов деления не спасает. 1/3 и в длинной арифметике непредставима, а sqrt(2) и в виде рациональных дробей. Я вижу проблему только с резким ростом вычислительной погрешности в операциях вроде 100500 ^ sqrt(3). Но для одного конкретного числа 10958 таких ситуаций мало, их можно и по одной (или классами) руками рассмотреть.
По крайней мере у меня получалось рассмотреть все лесенки из степеней, чтобы показать, что там 10958 точно нет. Чего я не рассмотрел, так это проблемы вычислительной погрешности, которые описал выше.
И да, я считаю (и это было в оригинале) что задача поставлена в действительных числах, не выходя в комплексную плоскость.
Комментарий пока не оценивали 0
Как отсекали выражения вроде ${({2}^{{3}^{{4}^{5}}}+6)}/{({7}^{{8}^{9}})}$? Если делимое можно по модулю 10958 легко посчитать, то с частным такое не выйдет. Или вы только простые лесенки вида $а+{{b}^{{(b+1)}^{(b+2)}}}$… рассматривали?
Комментарий пока не оценивали 0
Я рассматривал все сочетания лесенок высотой 3 и 4, их не много, можно разбить на классы и все рассмотреть на бумаге. Сейчас точно не воспроизведу, доказательство не сохранял, уже уверен, что в нём есть дыры, раз уж никто до сих пор полноценно задачу не решил.
Комментарий пока не оценивали 0
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Разблокировать темную тему

Истории

Ваш аккаунт

Разделы

Информация

Услуги

Техническая поддержка
© 2006–2024, Habr