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