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

[eugrita]

В 20 в с зарождением кибернетики и информатики традиционное понятие математики – функция расширилось.Если раньше функции в основном описывались формулами и на этом был построен матанализ, то теперь (кажется) Тьюрингом было введено понятие «вычислимая функция», т.е функция задаваемая не обязательно формулой но алгоритмом. Т.е.по входному параметру X которого вычисляется выходное значение Y. При этом алгоритм может еще быть рекурсивным или частично рекурсивным. В теории алгоритмов и логике были введены классы:
примитивно рекурсивных функций (ПРФ),
общерекурсивных функций (ОРФ) и
частично рекурсивных функций (ЧРФ).
школьники и сейчас изучают sinx, cosx, tgx,arcsin,arccos,arctg, expx,lnx, x^a, |X|. Эти и выражения из них есть класс ЭФ (элементарных функций) Он.реализован в инженерных калькуляторах
Более широким является класс ЭФИ -интегралов от выражений из ЭФ – он приводит к некоторым новым: бетта, гамма,интегральному cos, sin, ln ,интеграл вероятности, эллиптических .
операция численн интегрирования – это алгоритм.
Отметим шаткость понятия «элементарная функция": тот же lnx можно определить не как обратную к exp, а через интеграл от dx/x
Известны (проект Бейтмана) "специальные функции" СФ - расширение ЭФИ - туда входят еще решения дифференциальных уравнений составленных из ЭФ и функции-ряды (гипергеометрическая)
Для простоты ограничимся вычислимыми функциями 1 вещественного переменного.
Постановка вопроса:
1. Привести примеры других классов вычислимых функций отличных от ЭФ и ЭФИ и может даже СФ. Желательно гладких, т.е. непрерывных и дифференцируемых. Построить графики
(очевидный пример рекуррентных последовательностей не годится из за дискретности аргумента)
2. Проанализировать вопрос о применимости построенных функций к прикладным задачам.
(Прим. Отметим часто справедливую критику математиков представителями других наук, что те якобы погрязли в чистом искусстве. Действительно, изобретение новых функций часто инициируется задачами практики той же физики или экономики. А просто изобретать что-то с непонятной возможностью применения – чистое искусство.
В статистике и эконометрике ухитряются вести обработку данных с узким классом полиномов, экспонент

[ewert]

eugrita в сообщении #309727 писал(а):

1. Привести примеры других классов вычислимых функций отличных от ЭФ и ЭФИ и может даже СФ.

Т.е. таких, которых нет в справочниках?...

Сейчас попробую...

Как насчёт решения дифференциального уравнения $y'(x)=x\ln(y^2+\sin x)+e^{2x\over y^2}$ с начальным условием $y(0)=1$?...

[eugrita]

Согласен. Только 2 замечания.
1.Это -класс СФ. А я хотел вычислимую, но вне класса СФ
2.какова практическая польза данной функции? Какую вы видите пользу от программной реализации наподобие как в инженерных калькуляторах или вычислительных средах Mathcad,Mapple поддержки операций с СФ

[ewert]

eugrita в сообщении #309734 писал(а):

вне класса СФ

а что такое "класс СФ"?...

eugrita в сообщении #309734 писал(а):

какова практическая польза данной функции?

а ну как такой дифур на практике подвернётся?...

[eugrita]

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

[ИСН]

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

[ewert]

eugrita в сообщении #309742 писал(а):

Меня интересуют, есть ли непрерывные функции не являющиеся решениями дифф.ур, не вычисляемые как сумма рядов (т.е не средствами матанализа)

Пожалуйста: скажем, функция $y(x)$, определённая как неявно заданная уравнением $e^y+xy=0$ (вполне важная функция). Т.е. её тоже можно, конечно, свести к какому-нибудь дифуру, но считается-то она на практике совсем иначе.

Или: $\lambda_k(\alpha)$ -- зависимость от $\alpha$ для $k$-того собственного числа оператора типа $-{d^2\over dx^2}-{\alpha\over\sqrt{x^2+\cos x+2}}$.

Дело в том, что в анализе -- очень много разных средств. Потенциально -- наверное, бесконечно много. Термин же "специальные функции" -- не более чем лирический.

[eugrita]

Т.е вы добавили оператор взятия обратной функции.
Но я в исходном сообщении допускал возможность композиций функций класса
и тем самым (видимо не четко было произнесено) и возможность применения оператора "обратная функция".
Тогда переформулирую тезис.
Есть ли вычислимая функция т.е представимая алгоритмом, но не представимая
ни формулой термами которой являются ЭФ,подстановки, операторы интегрирования, терм - даже не решение дифф.ур, терм не является также функцией обратной к некоторой из класса ЭФ, ЭФР, CФ.
Т.е если такие функции есть оставим за собой право строить формулы из них как из кирпичей но более общего вида чем классические

[ewert]

да не переберёте Вы все мыслимые термы. К примеру: куда у Вас подевались интегральные уравнения?... И это лишь пример.

[ИСН]

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

[ewert]

(Оффтоп)

ИСН в сообщении #309781 писал(а):

Ваши требования, eugrita, не факт, что вообще формализуемы корректно.

Ну формализовать-то можно. Типа: "специальной функцией будем называть такую, которую можно как бы как-нибудь в некотором смысле посчитать".

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

[Maslov]

eugrita, объясните, пожалуйста, что в Вашем понимании означает "вычислимая функция"?
Если это функция, вычисляемая некоторым алгоритмом, то каким алгоритмом вычисляется, например, $\sin x$ или $\int \limits_0^x \sqrt {1 - k x^2} dx$?

eugrita в сообщении #309727 писал(а):

операция численн интегрирования – это алгоритм

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

[ewert]

Maslov в сообщении #309787 писал(а):

eugrita в сообщении #309727 писал(а):

операция численн интегрирования – это алгоритм

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

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

Другое дело, что на квадратурных формулах (и вообще на интегрировании) свет клином не сошёлся. А перечислять все мыслимые подходы, как говаривал тов. Екклезиаст -- "утомительно для тела".

[Maslov]

ewert в сообщении #310078 писал(а):

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

Под вычислимой функцией обычно понимается функция, для которой существует алгоритм ее вычислиения, т. е. процедура, которая
- если значение функции для заданного значения аргумента $x$ определено, останавливается после конечного числа шагов и выдает $f(x)$
- если значение функции для аргумента $x$ не определено, не останавливается на входе $x$
(в подавляющем большинстве случаев в теории вычислимости вообще рассматриваются только функции $\mathbb N \to \mathbb N$).

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

[eugrita]

Maslov в сообщении #309787 писал(а):

то каким алгоритмом вычисляется, например, $\sin x$ или $\int \limits_0^x \sqrt {1 - k x^2} dx$?

Ну тут нет проблем. для программиста sin вычисляется вызовом библиотечной функции. Самая хохма (на другом форуме) когда в редком случае возникает необходимость написать свой быстрый алгоритм вычисл sin - посоветовали в программу забить таблицу Брадиса. А реально - все- таки разложением в неск членов ряда Тейлора, обычно через tg
tan(x) = x/(1-x2/(3-x2/(5-x2/(7-x2/...)))).
Для single precision требуется 4 итерации, для double - 6-7.
А интеграл конечно по ф-лам численного интегрирования - трапеций, симпсона или др.