logo
МЛиТА 6 - 7

Простейшие функции

Функции s: N  N, : N  N и Inm:  Nn  N, принимающие значения s(x)  =  x + 1, (x)  =  0 и Inm(x1,…,xn)  =  xm, для всех x, x1,…,xn    N и n    m    1, называются простейшими. Операции над функциями будут называться операторами.

Выделим операторы, с помощью которых будут строиться вычислимые функции. Применяя эти операторы к простейшим функциям, мы получим частично рекурсивные функции.

Композиция частичных функций

Частичные функции f: A  B можно определить как функции, заданные на некоторых подмножествах Dom(f)  A и принимающие значения в B. Если Dom(f)  =  A, то f называется определенной всюду. В некоторых случаях частичные функции удобно рассматривать как определенные всюду. С этой целью к каждому множеству добавляется бесконечно удаленная (или отмеченная) точка . Произвольная частичная функция f: A  B расширяется до функции : A  {}  B  {} по формулам (x) = f(x) для x    Dom(f) и по формулам (x) =  для всех остальных x, включая . С другой стороны, каждая функция : A  {}  B  {} определяет частичную функцию g: A  B, принимающую значения g(x)  = (x) для x    -1(B). Ясно, что область Dom(g)  = -1(B) состоит из точек, не отображающихся в бесконечно удаленную. Соответствие, сопоставляющее частичным функциям f функции является взаимно однозначным. Рассматривая частичные функций f как их расширения , легко определить композицию частичных функций f: A  B и g: B  C. Если f и g определены всюду, то композиция совпадает с обычной. В общем случае область определения композиции gf состоит из точек x  A, таких, что g(f(x))  .

Пусть f1,…,fn: Nm  N – частичные функции. Определим частичную функцию (f1,…,fn): Nm  Nn, полагая

(f1,…,fn) (x) = (f1(x),…,fn(x))

для всех x  Dom(f1) …  Dom(fn) Nm.

Пусть f1,…,fn: Nm  N и g: NnN – частичные функции. Оператор суперпозиции (или композиции) Sn+1 сопоставляет им частичную функцию:

Sn+1(g, f1,…,fn) = g  (f1,…,fn).

Областью определения частичной функции g  (f1,…,fn) является подмножество точек x = (x1,…,xm)  Dom(f1) … Dom(fn), для которых (f1(x),…,fn(x))  Dom(g).