Нерешаемые уравнения.

[arseniiv]

У меня есть схожий вопрос, думаю, как его формализовать правильно, может, так?:

Возможно ли выразить в элементарных функциях / функциях заданного класса через решения (или какое-нибудь фиксированное решение, удовлетворяющее заданному предикату $P$) уравнения $F(x, a_1, \ldots , a_n) = 0$ решения уравнения $F(x, b_1, \ldots , b_n) = 0$ для $\left(b_i \right)_i \in A$ (и на каком максимально возможном $A \ne \varnothing$)?

Пример: Допустим, мы доказали, что всегда у уравнения $x - \sin x = a$ существует хотя бы одно неотрицательное решение и обозначили через $\xi_a (x)$ наименьшее из неотрицательных таких решений. Возможно ли найти элементарную функцию $f$ двух переменных такую, что $\xi_b (x) = f(\xi_a (x), x)$.

-- Пн дек 13, 2010 21:08:50 --

У него есть алгоритм решения?

Прошу прощения у Kitozavrа за захват темы.

[Xaositect]

Kitozavr в сообщении #386903 писал(а):

Я хотел бы знать, существуют ли уравнения, для которых нельзя найти неизвестное (вот скажу, что подбор не в счёт, и всё начнётся сначала).

Ну так весь вопрос и состоит в том, что значит "нельзя найти".

[venco]

Ну и ещё - что такое "элементарные функции".

[Legioner93]

Попытаюсь помочь ТС сформулировать. Решить уравнение $f(x)=0$ в том смысле, что хочет Kitozavr, это значит найти равенства вида $x_{i}=G(g_{1},...,g_{k})$, где $g_{1},...,g_{k}$ - заданный заранее класс функций над некоторым полем(наверное, необязательно над полем, вообще говоря. Пусть будет множеством), $G$ - композиция конечного числа функций из этого класса. $x_{i}$,$i=1..n$ корни уравнения в том же поле(множестве), на котором определены функции $g_{1},...,g_{k}$. При этом в класс функций могут входить бинарные операции $+,\cdot,...$ (ведь их тоже можно считать функциями от двух переменных), а также тождественная функция. И доказать отсутствие других равенств такого же типа (доказать отсутствие других корней). Ну как? Как-то коряво вышло.

-- Пн дек 13, 2010 20:57:21 --

А, еще нужно добавить, что аргументами функций могут быть либо другие функции (что обеспечивает суперпозиция), либо число из заданного поля (множества), записанное определенным образом (например в виде конечной или бесконечной периодической десятичной дроби). Это нужно для того, чтобы, например, при решении в элементарных функциях в поле действительных чисел нельзя было записать $x=W(1)$ и сказать, что это никакая не функция Ламберта от единицы, а просто обычное действительное число.

[Mathusic]

ТС скорее хочет задать вот такой вопрос: существует ли ур-е $f(x)=0$, где $x$ не может быть выражен в виде $F(a_1,a_2,\cdots,a_n), a_i \in \mathbb{R}$ ($F,f$ - элементарные)?

Ну а множество эл-х ф-ций $\mathfrac{S}$ можно определить по индукции, как множество всех суперпозиций некоторого набора ф-ций $\Omega.$ В частности, рассмотреть, когда $\Omega$ содержит привычные рацдроби, тригфункции, показательные ф-ции и т.д.

-- Сб дек 18, 2010 20:55:23 --

Legioner93 в сообщении #386953 писал(а):

Как-то коряво вышло.

Здесь вы что-то сущностей сверх меры намножили: ТС не подразумевал групп, полей, алгебр и т.д. и т.д.
Хотя, конечно, если сформулировать вопрос над произвольной универсальной алгеброй, он будет мало чем отличаться от сформулированного выше.
А вообще, конечно, идея практически такая же, вы только не говорите о формализации понятия "суперпозиция".

[arseniiv]

(Оффтоп)

А мой вопрос решаем как-нибудь?

[Circiter]

2Kitozavr

Цитата:

Интересно, а существуют ли уравнения, которые не возможно (решить) аналитически?

Возможно, под "аналитичностью" вы подразумеваете возможность получить решение с помощью цепочки символьных манипуляций и тождественных преобразований? Так? Тогда да, существуют. Хотя, конечно, вопрос более тонкий. Ну не всякая же неявная функция, будучи к чему-нибудь приравненной, "нерешаема". :)

Цитата:

И если существуют ,то как доказать, что данное уравнение относится именно к таким?

Ну, например, для дифуров, это всякие там неинтегрируемости (в некотором смысле). Cf. задача трех тел. Ещё близко к вашему вопросу подходит понятие детерминированного хаоса, когда даже при отсутствии погрешностей и случайностей сложно узнать будущее динамической системы без прямого моделирования её эволюции, а с погрешностями так и вообще... :)

[robez]

(Оффтоп)

У меня есть пример, но не совсем по уравнению.
Проблема в теории программирования именуемая "трассировкой требований к проекту" - нерешаемая формально или аналитически, но решаемая в лоб ручками. Представим себе любую программу. Лучше небольшую пусть даже не более 100 строк кода. Представим ситуацию, когда менеджер подряд выдвигает требования по изменению указанной программы, всего штук 10 не более. Каждое требование в отдельности можно рассматривать как преобразование текста программы. Каждое требование и их порядок независим от других, поскольку менеджер может формулировать требования в любом порядке - на то он и менеджер.

Кажется что преобразования могут формулироваться аналитически, например удовлетворять аксиоматике теории групп:
1) Для каждого преобразования существует обратное.
2) Существует преобразование которое ничего не меняет.
3) Результат двух последовательных преобразований не зависит от перестановки местами очередности этих преобразований.
4) И вроде бы что-то еще, не помню.

На самом деле мы не может уточнить, что же понимается под каждым из преобразований. Можно сколько угодно накапливать опыт предыдущих преобразований в разных комбинациях, но если встретиться очередность которой еще не было, у нас единственный выход - посмотреть что напрограммировал программист и включить как есть это в нашу базу знаний. при этом сама формулировка требований, а значит и суть преобразований, сильно зависит от того, какие преобразования уже сделаны. Уточнения в описании требований очень быстро накапливаются (Если уже выполнено требование 1 то требование 2 будет выглядеть немного по другому) и их сложность очень быстро (менее чем за 10 преобразований) многократно превзойдет сложность самой программы. Не надо думать что дело тут в простоте программы, для сложных программ и требования сложные. А уточнения ростут в сложности еще быстрее чем для простых программ.

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

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

[Legioner93]

robez в сообщении #389807 писал(а):

3) Результат двух последовательных преобразований не зависит от перестановки местами очередности этих преобразований.

Это почему?

[Ales]

Kitozavr в сообщении #386903 писал(а):

Я хотел бы знать, существуют ли уравнения, для которых нельзя найти неизвестное (вот скажу, что подбор не в счёт, и всё начнётся сначала). У меня есть подозрение что уравнение $2^n = n^2$ относится к таким.

Уравнение $3x=1$ тоже не имеет точного решения ни в целых числах, ни в десятичных дробях.

Никто не может решить диофантовы уравнения второй степени общего вида.

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