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

[ewert]

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

Любой конкретный алгоритм численного интегрирования c этой точки зрения не является эффективной вычислительной процедурой,

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

[Maslov]

Ну да. Поэтому я и спросил, что ТС понимает под вычислимыми функциями. Потому что его понимание этого термина, судя по всему, расходится с тем смыслом, который вкладывается в него в теории вычислимости. По крайней мере, насколько я знаю, понятия частичнорекурсивной, общерекурсивной и примитивнорекурсивной функции прменимы только к функциям $\mathbb N^m \to \mathbb N$.

[Ashley]

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

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

[eugrita]

Т.е вы говорите вообще об конструктивном подходе в математике?
Да, к сожалению (или к счастью) математика (как и философия) остается полем битвы разных направлений. И далеко не всегда ясно даже ученому за кем будущее и к чему примкнуть...
У меня цели были скромнее - как писал посмотреть, есть ли вообще какие-то полезные а не "декоративные" функции, вычисляемые алгоритмом но не средствами матем.анализа. (т.е на этом заодно и проверить, что понятие "алгоритм" само по себе мощнее всех разделов матанализа вместе взятых, включая и функционалы и операторы интегрирования/дифференциров)
Ну в общем мне уже кое-кто подсказал еще один класс функций
именно функции-решения нелинейного уравнения, скажем с 1 параметром a
(при соблюдении условия единственности).
Но что дальше с ним прикажете делать? Важен он или нет?
Все зависит от функции а их великое множество.
Т.е. я еще раз прихожу к мысли, после обсуждения, что если делать программу "построитель функций" профессионально, то кроме уровня инженерного калькулятора, туда надо закладывать дифференцирование-интегрирование (численным методом), решение нелинейных уравнений. И возможно еще что. Но тогда это бует даже не калькулятор, а целая вычислительная среда наподобие mathcad, matlab,mapple

[Ashley]

Я говорю о теории вычислимости, в ней наиболее полный и общий ответ на вопросы типа вашего

Дело в том, что у той теории вычислимости, которую например у нас дают в курсе матлогики, да?, есть продолжение: в терминах вычислимости возможно определение уже "вещественных" чисел, функций и всего прочего, которое разворачивается в целую математику не менее содержательную чем классическая.

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

В общем, я просто немного сомневаюсь: точно ли одно и то же конструктивизм с "конструктивным анализом" и в каком все-таки смысле понимается отрицание "закона исключения третьего" и всего такого прочего? И я думаю, отдельную тему мне бы создавать не стоило

[ewert]

Ashley в сообщении #310617 писал(а):

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

Я лично, будучи непричастен ко всем этим игрищам вокруг конструктивностей, всё-таки скромно заподозрю, что это -- одно и то же.