Математическое введение в декларативное программирование. Зюзысов В.М. - 67 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

= λ x y.((uncurry E) (x, y))
≡ λ x y. ((λ f p. f (fst p) (snd p)) E (x, y))
= λ x y. (E (fst (x, y)) (snd (x, y)))
= λ x y. E x y
→
η
•
•
•
•
•
•
E
Аналогично доказывается второе равенство. Нетрудно увидеть, что
sum = uncurry add
add = curry sum
9.2.6 Представление вычислимых функций
Один из подходов к формализации понятия алгоритма принадлежит Гёделю и Кли-
ни (1936). Основная идея Гёделя состояла в том, чтобы получить все вычислимые функ-
ции из существенно ограниченного множества базисных функций с помощью простейших
алгоритмических средств.
Пусть N обозначает множество натуральных чисел {0,1,2,...}. Объекты, которые мы
будем рассматривать, будут функциями с областью определения D
f
ΠN
k
(k - целое поло-
жительное число) и с областью значений R
f
Œ N. Такие функции будем называть k-
местными частичными. Слово «частичная» должно напомнить о том, что функция опре-
делена на подмножестве N
k
(конечно, в частном случае может быть D
f
= N , тогда функция
называется всюду определенной).
k
Множество исходных функций таково (x∈N
k
):
постоянная функция 0(x) = 0;
одноместная функция следования s(x) = x+1;
функции проекций pr
i
, 1 ≤ i ≤ k, pr
i
(x) = x
i
.
Нетривиальные вычислительные функции можно получать с помощью композиции
(суперпозиции) уже имеющихся функций. Этот способ явно алгоритмический.
Оператор суперпозиции. Говорят, что k-местная функция f(x
1
, x
2
, ..., x
k
) получена с по-
мощью суперпозиции из m-местной функции j(y
1
, y
2
, ..., y
m
) и k-местных функций
g
1
(x
1
, x
2
, ..., x
k
), g
2
(x
1
, x
2
, ..., x
k
), ..., g
m
(x
1
, x
2
, ..., x
k
), если
f(x
1
, x
2
, ..., x
k
) = j(g
1
(x
1
, x
2
, ..., x
k
), g
2
(x
1
, x
2
, ..., x
k
), ..., g
m
(x
1
, x
2
, ..., x
k
)).
Второй (несколько более сложный) способ действует так.
Примитивная рекурсия. При n ¥ 0 из n-местной функции f и (n+2)-местной функции g
строится (n+1)-местная функция h по следующей схеме:
h(x
1
, ..., x
n
, 0) = f(x
1
, ..., x
n
),
h(x
1
, ..., x
n
, y+1) = g(x
1
, ..., x
n
, y, h(x
1
, ..., x
n
, y)).
При n=0 получаем (a - константа)
h(0) = a;
h(y+1) = g(y, h(y)).
Две упомянутых способа позволяют задать только всюду определенные функции.
Частично-определенные функции порождаются с помощью третьего гёделева механизма.
Оператор минимизации. Эта операция ставит в соответствие частичной функции
f: N
k
+1
→N частичную функцию h: N
k
→N, которая определяется так:
1) область определения D
h
= {<x
1
,..., x
k
> | существует x
k
+1
¥0, f(x
1
,..., x
k
, x
k
+1
) = 0 и
< x
1
,..., x
k
, y> œ D
f
для всех y§ x
k
+1
};
2) h(x
1
,..., x
k
) = наименьшее значение y, при котором f(x
1
,...,x
k
, y) =0.
Оператор минимизации обозначается так h(x
1
,..., x
k
) = my[f(x
1
,..., x
k
, y) = 0]. Очевидно, что
даже если f всюду определено, но нигде не обращается в 0, то my[f(x
1
,..., x
k
, y) = 0] нигде не
определено. Естественный путь вычисления h(x
1
,..., x
k
) состоит в подсчете значения
67

Страницы