Главная
Проблема исчисления предикатов
Процедура унификации
Отношения на функциях принадлежности
Неразрешимые алгоритмические проблемы МТ
Полнота и непротиворечивость
NP-полные (универсальные) задачи
Стандартизация услуг
Стандартизация и экология
Организационные и методические принципы сертификации в России
Программа сертификации
Метрологический надзор
Структура кристаллов
Судьбы крестьянские
Еще одна фальшивая ценность
Такая судьба
Соприкосновение с рынком
Мой театр, мои коллеги
Гастроли
И жизнь и слезы и любовь
Возвращение из Томска
Реклама:
|
|
Полнота и непротиворечивость
определяемая оператором минимизации, не является вычислимой.
Одним словом в бесконечной таблице истинности нельзя найти 1, если ее там нет, но и нельзя сказать, что ее нет, не перебрав всех строк.
Такие предикаты приводят к понятию частичных функций, которые определены не на всех наборах своих аргументов. Ведь если функция не определена на наборе x1,…xn, то для этого набора y=f(x1,…xn) не существует, и предикат P(x1,…xn,y) кодирующий функцию, не сопоставит не одному y значение 1.
Частично рекурсивные функции, которые определены на всех наборах своих аргументов, называются общерекурсивными (аналог общезначимых формул).
Проблема применимости. Использование неограниченного оператора минимизации ведет к получению части
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
