Cтраница 3
В Pk при k 3 система всех одноместных функций параметрически полна, но не полна неявно. [31]
В Pk при k 4 система всех одноместных функций полна по неявной сводимости. [32]
Чтобы построить обратную матрицу, в АПЛ введена одноместная функция Щ, символ которой образуется наложением квадрата и символа функции деление. Обычно эту функцию называют домино или матричное деление. Поскольку данные для этого примера хранятся в 1 КЛАСС, скопируем эту рабочую область и воспользуемая обратной матрицей для X для решения задачи нахождения единицы стоимости товаров. [33]
Следующая теорема показывает, как можно порождать все одноместные функции некоторого класса, не выходя за рамки множества одноместных функций. [34]
ЧАСТИЧНО РЕКУРСИВНЫЙ ОПЕРАТОР - - отображение класса всех одноместных функций в себя, определяемое следующим образом. Пусть Фг - нек-рый перечне к ни я оператор. С тим оператором естественным образом связан другой оператор Ч, к-рый действует на одноместных функциях. При фиксированном способе кодирования пар натуральными числами этот график может рассматриваться как множество т ( ф) натуральных чисел. В противном случае считают, что значение Ф ( () ие определено. [35]
Следовательно, W содержит один из следующих наборов одноместных функций. [36]
Поэтому для доказательства теоремы достаточно установить, что все одноместные функции из Q допустимы. [37]
Каждый из полученных наборов содержит один из следующих наборов одноместных функций. [38]
Существование базисов по суперпозиции в счетных примитивно рекурсивно замкнутых классах одноместных функций / / Матем. [39]
Пусть система функций из Pk, k 2, содержит все одноместные функции. [40]
Взяв диагонали этих функций, получаем, что должны найтись две одноместные функции, различающиеся только в единице. Нетрудно видеть, что хотя бы одна из них принимает не более двух значений. Снова воспользуемся леммой 3 и получим все константы. [41]
Такая система не является неявно полной, поскольку не содержит двух одноместных функций, различающихся только в двойке. [42]
Для простоты рассмотрим случай, когда на машине Ш идет вычисление одноместной функции ( х); случай многоместной функции отличается совершенно незначительными деталями. Будем также считать, что аргументы и значения представлены в унар ной записи; как уже отмечалось в § 11.1, это ограничение тоже несущественно. [43]
Так как каждая из указанных функций сохраняет некоторое нетривиальное разбиение, система одноместных функций из W, не сохраняющих общего разбиения, не может состоять только из одной функции. [44]
Итак, в классе [ Pol ( p) U д ] имеется одноместная функция gi, не сохраняющая предикат р ( ср. [45]