Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Categories:

Вычислимые вещественные функции

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

Начнём с определений вычислимого вещественного числа:

1) Т-вычислимое (Г-вычислимое) вещественное число задаётся целым числом (целая часть) и вычислимой (Г-вычислимой) функцией, генерирующей дробную часть в виде десятичной дроби, т.е. функция вида Nat => {0, 1,.., 9}. Допускаются бесконечные хвосты из девяток, т.к. упрощение числа 0.999... до 1 требует бесконечного числа операций (убедиться, что нигде дальше не встерчается цифр меньше девятки), а следовательно невычислимо. Если допускать такие хвосты, то перевод из одной системы счисления в другую вычислим, а следовательно для определения не важно, какую конкретно систему счисления мы используем.

2) Вычислимое вещественное число определяется вычислимой цепной дробью, т.е. функцией Nat => Nat. Если не настаивать на каноничности записи рациональных чисел (т.е. допускать единицы в конце цепной дроби), то конвертирование из 1 в 2 Г-вычислимая операция. В другую сторону, если взять первые n членов цепной дроби, то аппроксимация будет иметь точность не хуже 1/n, то есть если взять m^(n + 1) членов, то мы с запасом точности можем получить n-ную цифру m-ичного разложения.

3) Вычислимое вещественное число x задаётся вычислимой функцией, которая для каждого n: Nat выдаёт рациональное число отличающееся от x не более чем на 1/n. Рациональные числа кодируем парами [числитель, знаменатель]. Ясно, что данное определение эквивалентно 1 и 2 по уже упомянутым в 2 причинам.

Априорно непонятно, дают ли другие схемы нумерации рацинальных чисел дают эквивалентные определения вычислимости. Судя по всему, вообще говоря нет. Какими свойствами должно обладать кодирование, чтобы определение оставалось эквивалентным каноническому? Моё предположение: кодирование должно допускать Г-вычислимые сличение, сравнение, сложение, вычитание, умножение и деление.

4) (Прямое обобщение 3) Выбираются плотное в действительных числах счётное (пронумерованное) множество D и счётная база антуражей U на множестве вещественных чисел, у такой системы всегда есть естественная нумерация: 0 = антураж, включающий всё множество, а дальше каждый последующий антураж меньше каждого предыдущего, а в пределе n → ∞ — диагнональ. Теперь собственно определение: вычислимое действительное число x задаётся функцией f, которая для каждого n: Nat выдаёт аппроксимацию f(n): D, такую что x лежит в U(n)-окрестности f(n). Прелесть этого определения в том, что оно обобщается с вещественных чисел на вообще любые равномерные пространства со счётной базой. Но совершенно не очевидно, что разные базы антуражей U, разные множества D и разные нумерации последних дают эквивалентные определения. От D и его нумерации в соответствии с предположением выше естественно потребовать, чтобы все операции из сигнатуры подлежащей структуры были Г-вычислимыми. Давайте подумаем хорошо, какие условия требуются, чтобы 4 было эквивалентно 3! Я вот пока в процессе.

Теперь определения вычислимых функций разной степени удобства:
1) Вычислимая функция на действительных числах просто вычислимая функция, сопоставляющая действительным числам в кодировании 1-3 действительные числа в кодировании 1-3. Это определение, насколько я понимаю, очень непрактичное. С одной стороны, оно позволяет задавать сколь угодно паталогические функции, с которыми дальше невозможно работать, с другой многие нужные вещи оно не позволяет задать, т.к. для подсчёта n-ного знака десятичного разложения результата какой-нибудь вполне естественной математической функции, вообще говоря может понадобиться знать все знаки аргумента, а это невычислимо.

Очень удобным является следующее определение вычислимых кусочно-гладких функций:
2) -"- задаётся вычислимой функцией из рациональных чисел (в вышеупомянутом кодировании) в вещественные числа (в кодировании из 1-3). Однако вообще говоря нам часто может быть удобно взять другое плотное множество — какое-нибудь подмножество рациональных или алгебраических чисел. Отсюда желательное обобщение:
3) -"- задаётся выбранным счётным плотным подмножеством D действительных чисел с выбранной нумерацией, допускающей Г-вычислимые операции сравнения, сличения, сложения, вычетания, умножения и деления, и функцией D => RR, где RR действительные числа в кодировании из 1-3.

Мне кажется, определение 3 замкнуто относительно обращения функций, интегрирования и дифференцирования, всех известных мне сходящихся численных алгоритмов, под него подходят решения дифференциальных и интегральных уравнений наиболее широких известных классов. Так ли это? Давайте порассуждаем, чем оно хорошо или плохо.
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments