Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Доказательство окончено. Доказанная теорема позволяет сформулировать следующее утверждение: всякая интуитивно вычислимая числовая функция может быть вычислена подходящей системой




Доказанная теорема позволяет сформулировать следующее утверждение: всякая интуитивно вычислимая числовая функция может быть вычислена подходящей системой Поста.

 

Этот тезис носит название тезиса Поста. Его справедливость следует из тезиса Черча и доказанной возможности вычисления всякой частично-рекурсивной функции с помощью систем Поста.

 

Следовательно, функциональные возможности систем Поста такие же, как и у программ, составленных на одном из универсальных языков программирования. Совпадение множеств функций, вычисляемых системами Поста, и частично рекурсивных функций позволяет использовать знания, о рекурсивных функциях при изучении возможностей систем Поста. Например, рассмотрим задачу о выводимости в системах Поста множества слов, являющегося дополнением множества слов, выводимых в некоторой системе Поста.

Теорема 9.5. Существует система Поста P = (A, B, V, P), такая что множество (A È B)* \ WP не является множеством слов выводимых в системах Поста.

Доказательство.

Пусть U (n, x) универсальная частично рекурсивная функция для множества всех одноместных частично рекурсивных функций, определенная в главе 8. Рассмотрим вспомогательную функцию:

Поскольку функция h является вычислимой, то существует вычисляющая h система Поста П h = (A h, B h, V h, P h), и не существует системы Поста П H = (A H, B H, V H, P H), такой что A h = A H и = (A h)* \ .

Последнее утверждение является верным, поскольку существование системы П H влечет разрешимость множества
A 1={(n, x)½значение fn (x) определено}, определенного в главе 8. Характеристическую функцию этого множества можно вычислять с помощью следующего алгоритма:

1. Пусть требуется определить принадлежность элемента множеству (n, xA 1.

2. С помощью алгоритмом построения всех конечных выводов в произвольных системах Поста организуем последовательное заполнение множеств и .

3. Продолжаем процесс до тех пор, пока или не будет включено слово h (n, x) = 1.

4. Если слово h (n, x) = 1 добавляется во множество , то (n, xA 1. Если слово h (n, x) = 1 добавляется во множество , то (n, xA 1.

Поскольку слово h (n, x) = 1 обязательно выводится в одной из систем Поста или , то приведенная процедура за конечное число шагов определяет принадлежность произвольной пары (n, x) множеству A 1.




Поделиться с друзьями:


Дата добавления: 2015-03-31; Просмотров: 369; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.