Поскольку одно и то же число может быть записано в различных системах счисления, встает вопрос о переводе представления числа из одной системы (р) в другую (q) - будем обозначать такое преобразование Zp → Zq. Теоретически возможно произвести его при любых q и р. Однако подобный прямой перевод будет затруднен тем, что придется выполнять операции по правилам арифметики недесятичных систем счисления. По этой причине более удобными с практической точки зрения оказываются варианты преобразования с промежуточным переводом Zp → Zr → Zq с основанием r, для которого арифметические операции выполнить легко. Такими удобными основаниями являются r =1 и r = 10, т.е. перевод осуществляется через унарную или десятичную систему счисления.
Преобразование Zp → Z1 → Zq
Идея алгоритма перевода предельно проста: положим начальное значение Zq:= 0; из числа Zp вычтем 1 по правилам вычитания системы р, т.е. ZP: = ZP – 1* и добавим ее к Zq по правилам сложения системы q, т.е. Zq:= Zq + 1; будем повторять эту последовательность действий, пока не достигнем Zp = 0.
* Знак «:=» используется здесь и далее в смысле «присвоить» («считать равным»).
Правила сложения с 1 и вычитания 1 могут быть записаны следующим образом:
Промежуточный переход к унарной системе счисления в данном случае осуществляется неявно - используется упоминавшееся выше свойство независимости значения числа от формы его представления. Рассмотренный алгоритм перевода может быть легко реализован программным путем, в частности, машиной Тьюринга (см. п.7.3.3).