Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Постановка вопроса - часть 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 сами были вычислимы в интуитивном смысле.
Конкретные алгоритмы работают всегда с представлениями натуральных чисел.
Нужно, чтобы конкретные представления были также реалистически приемлемы для обращения. Поэтому предполагается, что Т есть конечное множество.
