Комментарии 39
Сама задача Танежи обнажает проблему полного дискретного представления и показывает несостоятельность популярных методов описания структуры данных при решении математических задач на ПК
Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача. Так было с формальным обоснованием невозможности построения квадратуры круга циркулем и линейкой, с малой проблемой Гольдбаха и рядом других математических проблем. Так происходит и сегодня. Постановка задачи о представлении натуральных чисел при помощи семи операций над некоторым начальным вектором, подарила миру не только красивые частные решения и загадочную константу 10958, но и особый подход к классификации величин, значения которых не всегда могут быть записаны в явном виде. Так, доказано, что радикальные числа имеют ненулевое пересечение с множеством алгебраических чисел, но не входят в последнее полностью.
Часто следствия из теорем, доказательство которых было необходимо при решении некоторой задачи, оказываются ценнее, чем сама задача.
При аналитическом подходе к решению задачи Танежи в восходящем порядке естественным образом возникает понятие конечно-трансцендентного числа. И за это мы благодарны Индеру Танеже. Но сам он никакой классификацией трансцендентных действительных величин не занимался. Об этом идёт речь. Мы ценим не саму возможность представления целых при помощи замыкания над множеством чисел от 1 до 9, а ту математическую теорию, которая благодаря изучению этой возможности возникает.
Пожалуйста, уберите длинные простыни кода и вывода под кат. Мотивация дочитать до конца и понять сильно повысится.
Кончились задачи, которые можно решить в одиночку, не будучи супергением.
FTFY.
Нерешённых (вопрос, считать ли их все актуальными?) проблем в математике — море: https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_mathematics.
У физиков (и не только) тоже дофига задач, где математики могли бы помочь. К сожалению, часто это задачи вычислительного характера, которые математикам неинтересны (простой пример: выразить решение дифференциального уравнения Х либо через известные спецфункции, либо в виде интеграла и т.п.). Поэтому, в основном, такими задачами занимаются не собственно математики, а математические физики.
В чём физический смысл теоремы Ферма или диофантовых уравнений? Наверное, ни в чём, но при решении связанных с ними задач была придумано масса методов, были найдены неожиданные связи между геометрией и алгеброй и т.д… Попытки оценить плотность простых чисел внесли вклад в развитие комплексного анализа, были получены многочисленные тождества для всяких спецфункций, которые через пару сотен лет неожиданным образом оказались нужны для физики.
В общем, синтетические задачи — это не обязательно плохо. Часто они являются драйвером развития общих математических методов.
Есть такое замечательное понятие: Гильбертова интуиция. Оно поможет вам понять, что происходит.
Давид Гильберт — немецкий математик XIX-XX веков. На втором международном математическом конгрессе 1900 года он предложил 23 «фундаментальные» задачи современной (ему) математики и обосновал их значимость весьма оригинальным образом.
Рассмотрим поведение профессионального математика при решении некоторой задачи. На первом этапе решения математик пытается получить наиболее простую (так называемую «рабочую версию») формулировку задачи. Речь не всегда идёт о простоте в научно-популярном смысле, как это происходит сейчас с проблемой Гольдбаха-Виноградова и проблемой Эрдеша. Математик ищет простую для себя формулировку. Так не секрет, что без ограничения общности некоторой геометрической задаче можно поставить в соответствие алгебраическую модель. А задачу из теории чисел, наоборот решать в топологиях. И если наш герой более компетентен в геометрии, он будет искать наиболее понятную геометрическую трактовку для большинства задач, вне зависимости от раздела-источника задачи.
На втором этапе происходит процесс «эвристического поиска уязвимостей». Решая однотипные задачи математик не развивается — такие упражнения полезны при подготовке к ЕГЭ, выступлении на олимпиадах — не более. Но рассматривая задачи с принципиально разным подходом к решению, относящиеся к некоторой узко специальной области, ученый формирует ряд ложных корреляций, которые составляют математическую интуицию. Так, имея на начальном этапе несколько путей анализа задачи, математик с опытом может «наугад» выбрать тот путь, который с большей вероятностью приведёт к стройному решению.
Наряду с интуицией отдельного математика, Гильберт рассматривает коллективное «ощущение важности» некоторых задач для всего математического сообщества. Так, диофантово уравнение уже на тот момент не являлось единственным нерешаемым неопределённым уравнением в целых числах, однако «математическое чутьё» подсказывало, что при решении именно этого уравнения возникнет необычайно ценный математический аппарат, который будет применяться в различных областях науки.
Гильбертова интуиция — это способность отобрать из числа бесполезных задач как таковых (ибо нахождение корней для уравнения не несёт ничего полезного) — те, с решением которых престиж математики, возможности теоретического аппарата и уровень влияния на другие науки возрастут.
Задача Танежи как таковая не несёт пользы, но для её решения (как оказалось при детальном рассмотрении, результаты которого частично приведены в этой статье) потребуется развить трансцендентологию и расширить современную дискретную математику теорией ПДП. То, как сильно современные астрофизика, нейробиология и ряд других прикладных дисциплин зависят от дискретки думаю пояснять не требуется.
i это поворот вектора на π/2 через комплексное направление, поэтому i2 это поворот на π, что эквивалентно умножению на -1.
i1/2 это поворот на π/4, а его проекции на координатные оси равны √2/2 = (1/2)1/2.
это поворот на , а его проекции на координатные оси равны .
Интересная идея! Действительно, некоторые комплексные величины, целая и мнимая часть которых являются целыми числами, либо для которых существует тригонометрическая форма записи с рациональными углами (в градусном их измерении), в точности представляют такие иррациональные значения, как и позволяют выполнять некоторые операции над этими значениями без погрешности.
Также, мне кажется тема «нормальных» чисел более фундаментальна
Интересно, это как нибудь связано с мерой рациональности числа?
Если вы имеете в виду «меру иррациональности», то она является оценкой возможности приближения некоторого действительного числа конечным набором целых значений. ПДП же предполагает точное представление иррациональных и трансцендентных чисел на компьютере и выполнение операций над ними без погрешности. Поэтому прямая связь отсутствует. Если же будет доказана связь между мерой иррациональности и qtrans, то тогда можно будет подискутировать.
Также, мне кажется тема «нормальных» чисел более фундаментальна
Для математики — да. Для прикладной информатики — тема «конечно-трансцендентных» сегодня важнее. К тому же, в работах математиков 2010-2020 годов слишком часто стали появляться высказывания о «беспомощности» современной алгебры при работе с трансцендентными величинами. Пока даже доказательство факта трансцендентности является нерешаемой задачей для большинства классов действительных величин. Например: трансцендентность десятичных логарифмов целых, отличных от степени десятки, чисел была доказана, однако вопрос о трансцендентности логарифма числа, взаимно простого с основанием этого логарифма является открытой математической проблемой, не уступающей по «безнадёжности» ABC-гипотезе.
Кстати, Вы не задумывались о том, что получение произвольного числа из вектора 123456789 и ограниченного набора операций близко к проблеме Collatz в ее инверсной форме: от 1 и двигаясь "назад" получить любое целое?
Всё зависит от того, как вы определяете понятие близости для двух математических проблем))
Задача Танежи как таковая проще проблемы Коллатца хотя бы потому, что требует разложения с использованием конкретного количества бинарных операций (а именно 8-и). Если же думать о Collatz как о сужении понятия конечной-трансцендентности для некоторого числа как принадлежность этого числа замыканию единичного множества относительно унарных операций , то можно как минимум показать что всякому элемента из множества (натуральных чисел) можно сопоставить элемент множества , но такое соответствие не обязательно является взаимно-однозначным. Пример:
Возьмем натуральное число 12. Запишем его в двоичной системе исчисления: . Тогда длину двоичной записи, уменьшенную на единицу (3) будем интерпретировать как количество операций, используемых при выводе соответствующего элемента из , а вектор цифр двоичного представления, записанных в обратном порядке без старшей цифры — как номера соответствующих операторов. Тогда для любого натурального числа количество операций может быть однозначно интерпретировано как длина единственного возможного двоичного представления и любой набор операций представим соответствующим натуральным числом (запись в обратном порядке и удаление старшей цифры были необходимы для того, чтобы такие выводы, как: и были представимы и различимы). Так число 12 производит элемент:
Дальнейшие перспективы решения проблемы Коллатца туманны. Так из факта существования ПДП для задачи Танежи следует её алгоритмическая разрешимость, в то время как для задачи Коллатца доказана её неразрешимость на некотором полном по Тьюрингу языке программирования (а именно, Fractran).
На практике — хранение неупакованных данных в памяти дешевле, чем затраты процессора на перепаковку
МБ для каких-то супер-пупер компьютеров это не так, там проц дешевле оперативы и тогда это будет иметь смысл. Но что-то я сомневаюсь в таких суперкомпьютерах
В статье дан ответ на этот вопрос. Если коротко и на примерах, то с такими числами как и работать на компьютере проблематично, а в теории то что — неочевидно и требует строгой проверки. И такие варианты, с которыми нельзя справится даже на суперкомпьютерах — составляют порядка 15% от общего числа выводов. Помимо этого, работа с иррациональными числами на компьютере как правило ограничена работой с их вещественным приближением. И для некоторого выражения: на компьютере можно получить лишь приближение: . Отсюда вытекает проблема полного дискретного представления для иррациональных и трансцендентных величин.
(1+2^3)*4-5=(1+8)*4-5=9*4-5=36-5=31,
а не 35, как у Вас написано.
PS: по-моему, никто еще не отметил эту ошибку
см. Точная формулировка и первые обобщения
Мне казалось, что отсутствие разложения уже доказано, ведь несложно показать, что среди лесенок из степеней этого числа нет, а всё остальное перебирается в лоб.
Но ведь при наличии среди допустимых операций вычитания и деления перебором задача так просто уже не решается...
Обе операции мешают установить верхнюю границу для перебора. Проблемы с точностью как раз ерунда, длинная арифметика давно уже для всех языков реализована.
Полный перебор (забив на все переполнения и неточности, поэтому и не полностью корректный как доказательство) в даблах на домашнем компе у меня занял 40 секунд. Длинная арифметика сразу увеличивает время в разы (что ерунда для глобальной задачи), но от точности и непредставимости результатов деления не спасает. 1/3 и в длинной арифметике непредставима, а sqrt(2) и в виде рациональных дробей. Я вижу проблему только с резким ростом вычислительной погрешности в операциях вроде 100500 ^ sqrt(3). Но для одного конкретного числа 10958 таких ситуаций мало, их можно и по одной (или классами) руками рассмотреть.
По крайней мере у меня получалось рассмотреть все лесенки из степеней, чтобы показать, что там 10958 точно нет. Чего я не рассмотрел, так это проблемы вычислительной погрешности, которые описал выше.
И да, я считаю (и это было в оригинале) что задача поставлена в действительных числах, не выходя в комплексную плоскость.
Задача Танежи: новый этап развития математики?