Универсальная функция

для данного класса Кфункций типа [img: http://localhost:8080/file/052105-113.jpg] - функция F(y, х1,..., х п)типа [img: http://localhost:8080/file/052105-114.jpg] такая, что для всякой [img: http://localhost:8080/file/052105-115.jpg] [img: http://localhost:8080/file/052105-116.jpg] найдется [img: http://localhost:8080/file/052105-117.jpg] при к-ром [img: http://localhost:8080/file/052105-118.jpg] Здесь [img: http://localhost:8080/file/052105-119.jpg] - множество натуральных чисел, а равенство (*) означает, что функции f(x1,..., х n)и F(i, x1,..., х n) определены на одних и тех же наборах аргументов x1,..., х n и их значения на этих наборах совпадают. Иногда в определении У. ф. требуется, чтобы для всех [img: http://localhost:8080/file/052105-120.jpg] функция F(i, x1,..., х n)принадлежала классу К(см. [4]). Имеются также др. варианты определения У. ф. (см. [1], [2]). У. ф. существуют для всякого счетного класса функций. Следующие У. ф. играют важную роль в теории алгоритмов: 1) универсальные частично рекурсивные функции для классов всех n-местных [img: http://localhost:8080/file/052105-121.jpg] частично рекурсивных функций,2) общерекурсивные У. ф. для классов всех n-местных примитивно рекурсивных функций. Если функция [img: http://localhost:8080/file/052105-122.jpg] универсальна для класса всех одноместных частично рекурсивных функций, то она не продолжается до рекурсивной всюду определенной функции, а множество [img: http://localhost:8080/file/052105-123.jpg] определена} является примером перечислимого, но не разрешимого множества натуральных чисел.