![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
p-адические числа в CS
Apr. 12th, 2014 11:42 amПри исследовании преобразователей потоков в 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.
Потоком или бесконечной последовательностю 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.
