Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

Category:

p-адические числа в CS

При исследовании преобразователей потоков в Computer Science естественным образом возникают p-адические числа.

Потоком или бесконечной последовательностю Stream T, где T некий дискретный тип данных, называется тип, оснащённый семейством сюрьективных функций taken: Stream T -> Vec n T, таких что для любого потока s и натуральных n и m первые min(n, m) элементов taken s и takem s совпадают.

На этом типе естественным образом задаётся топология: закрытая n-окрестность потока s определяется как множество потоков, совпадающих с s в первых n элементах (т.е. таких что taken у них совпадает). Непрерывные функции на этом типе суть продуктивные трансдьюсеры, т.е. такие преобразователи строк, что для вычисления конечного числа элементов результата нужно преобразовать лишь конечное число элементов аргумента. Количество знаков аргумента, которые нужно проанализировать, чтобы вычислить n знаков f(x) называется модулем непрерывности f и обозначается через |f|x(n). Если T конечный тип данных, то вышеназванная топология естественно метризуется функцией расстояния d(a, b) = {1/#Range(taken), где n длина совпадающего префикса a и b, }, если обозначить количество элементов в T через p, то формула упрощается до 1/pn = p-n.

Можно ли как-то алгебраически охарактеризовать непрерывные функции на потоках?

Для простоты сперва ограничимся именно такими потоками Stream T ≃ Stream (Fin p), где Fin p = {0, 1,..(p - 1)}. Можно рассматривать потоки s: Stream (Fin p) разложения натуральных чисел в p-ичной BIG-ENDIAN-кодировке и задать на них операции сложения и умножения через обычные алгоритмы сложения и умножения в столбик для натуральных чисел в BIG-ENDIAN-кодировке (кстати для них, чтобы узнать n-ный знак результата, требуется обработать лишь первые n знаков аргументов). Настоящим натуральным числам соответствуют лишь потоки, обращающиеся в нуль начиная с какого-то конечного n-ного знака, остальные числа это какие-то "бесконечно-длинные числа". Это не беда, главное что данное множество с данными операциями сложения и умножения образуют унитальное коммутативное кольцо без делителей нуля, обозначаемое как Zp (кольцо p-адических целых) и по теореме Малера все непрерывные функции f(x) на нём взаимно-однозначно задаются равномерно сходящимися разложениями вида Σn an x#n, где an последовательность p-адических целых, а через x#n обозначаются биномиальные коэффициенты (теорема Малера).

George Kapoulas установил, что вычислимые за полиномиальное время функции над p-адическими целыми образуют очень хороший, замкнутый относительно композиции и инверсии класс, в который входят входят функции taken, все преобразователи на базе конечных автоматов, все многочлены и все функции.
- Всякая полиномиально-вычислимая функция есть непрерывная функция на p-адических целых с модулем непрерывности, однородно ограниченным многочленом.
- Всякая непрерывная функция f(x) на p-адических целых, с модулем непрерывности, однородно ограниченным многочленом, представима через параметрическую полиномиально-вычислимую функцию g, т.е. f(x) = g(x, c1,.., cn) для какого-то конечного фиксирвоанного набора констант c1,.., cn.

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.
  • 8 comments