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