tgoop.com/covalue/57
Last Update:
Papayannopoulos, [2020] "Unrealistic Models for Realistic Computations: How Idealisations Help Represent Mathematical Structures and Found Scientific Computing"
Научные вычисления (scientific computing / computational science), т.е. общие техники для всех вычислительных ветвей эмпирических наук, можно разделить на символьные и численные методы, в статье идёт речь о последних. Т.к. численные методы работают с непрерывными значениями (действительными/комплексными числами и их обобщениями), появляются вопросы сходимости, устойчивости и вычислимости алгоритмов над плавающей арифметикой (в частности проблема накопления ошибок округления). Для изучения этих вопросов нужен математический фреймворк вычислений над несчетными множествами, из наиболее популярных это BSS model (aka Real-RAM) и computable analysis (aka Type Two Effectivity), причем друг с другом они несовместимы. Статья посвящена разбору этих двух подходов.
CA/TTE - более фундаментальная и "низкоуровневая" теория, это разновидность матанализа, где сохраняется классическая теория, но дополнительно учитываются вычислительные представления объектов через бесконечные аппроксимации. Как правило, это делается через работу с некоторыми разновидностями машин Тюринга (с оракулом или более сложной машинерией репрезентаций). Её появление можно отследить к трудам Бореля, Банаха и Тюринга 1910-30х годов, где рассматривались вычислимые подмножества R (эта идея получила развитие в Марковской школе конструктивизма/синтетической вычислимости). Более поздние подходы ("Хагенская школа") перешли к рассмотрению всего R (ключевая идея TTE). В этой модели вычислимые функции должны быть непрерывными - как следствие, мы теряем возможность полноценно использовать "точечные" функции сравнения и округления (ср. https://twitter.com/andrejbauer/status/1400172747930718209).
BSS - модель вычислений с идеализированной RAM-машиной, способной хранить в памяти произвольные числа (в т.ч. и точные значения действительных) и мгновенно производить арифметические операции над ними. Тут не возникает проблем с разрывными функциями, но усложняется работа с функциями алгебраическими и трансцендентными (с которыми нет проблемы у CA), начиная с банальных квадратных корней.
Какой же фреймворк предпочтителен? BSS менее реалистична и хуже подходит для работы с ошибками округления и плохо обусловленными функциями, но тем не менее довольно популярна - она моделирует устойчивые алгоритмы (т.е. не вносит собственных ошибок) и позволяет работать с оценкой их сложности. Также BSS ближе к алгоритмам плавающей арифметики в том, что имеет фиксированную стоимость операций (в отличии от CA, где стоимость зависит от входа). С другой стороны, CA подходит для более глубоких вопросов вычислимости (в т.ч., например, квантовой) и работы с "плохо ведущими себя" функциями, но создает больше проблем при анализе стоимости и работе с хорошо изученными численными алгоритмами.
В конце статья проводит аналогию с физическими моделями, облегчающими работу за счет нереалистичных упрощений, например, плавающие числа можно рассматривать как аналог экспериментальных значений - т.е., классическая и вычислительная математики живут в разных реальностях.
#realnumbers
BY Covalue
Share with your friend now:
tgoop.com/covalue/57