Частично-рекурсивные функции

Картезианским, или декартовым, произведением множеств A1, ..., An называется множество упорядоченных кортежей (n-ок) из элементов этих множеств.

A1×...×An = {(x1, ..., xn) | x1A1, ..., xnAn}.

Кортеж (вектор) значений

x ≡ (x1,...,xn).

Произведение на себя

An = A×...×A (n раз)

Многоместная функция (n-местная)

f ∈ [A1×...×AnB].

Частичная числовая функция имеет тип

f ∈ [Nn→N].

Рекурсия — способ задания функции путём определения каждого её значения через