Постановка вопроса - часть 2

С помощью этого перевода вместо абстрактного отображения между натуральными числами

f: N” -> N

рассматривается конкретное отображение между последовательностями знаков

f : (Т*)» -> Т*

со следующим свойством (для всех xj,..., Хn Î N):

f(xi, ..., Хn) = abs(f(rep(xi), ..., rep(Xn))).

Это равенств говорит, что , вместо того чтобы вычислять значение функции f для аргументов х1, ..., хn, можно определить представления гер(x1), ..., гер(xn) аргументов и для них вычислить значение f . С помощью функции abs можно из результата применения f к rep(x1), ..., rep(xn) получить значение функции для аргументов (Xi), ..., (Хn). Из приведенного выше равенства получается коммутирующая диаграмма, показанная на рис.9.1.

f

N”             N

Rep ­          abs¯

(Т*)»         T*

f

Рис. 9.1. Коммутирующая диаграмма

Эту схему отношений между абстрактным и конкретным представлением можно найти также во многих областях пошагового уточнения представления данных в программировании и относящихся к этому функций. Тогда говорится об аспекте абстракции.

Употребительными формами представления чисел являются представление соответствующим количеством штрихов, двоичное или десятичное представления и разложением на простые числа. Существует зависимость между сложностью вычислений и выбором конкретного представления. Для определения понятия вычислимости дополнительно требуется, чтобы функции гер и abs сами были вычислимы в интуитивном смысле.

Конкретные алгоритмы работают всегда с представлениями натуральных чисел.

Нужно, чтобы конкретные представления были также реалистически приемлемы для обращения. Поэтому  предполагается, что Т есть конечное множество.