Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Співвідношення між класами примітивно рекурсивних та елементарних функцій





Нехай , де носій El – клас елементарних функцій; – це операції.

Алфавіт:

Визначення операторного терму:

1. Усі символи базових функцій є операторними термами.

2. Якщо є операторними термами для завдання m-арних функцій, а є термом для задання n-арної функції, то терм є термом для позначення m-арної функції.

3. Якщо є операторним термом для бінарної функції, то терми є операторними термами для бінарних функцій.

4. Інших оператор них термів не існує.


Зрозуміло, що кожна елементарна функція є ПРФ. Доведемо зворотне твердження – що це включення строге.

Для цього розглянемо допоміжну функцію :

Функцію назвемо k -східчастою, якщо має місце умова: .


Теорема:
Довільна елементарна функція є k -східчастою для певного відповідного значення k.

Доведення:

· Базові функції:

o

o так само для ;

o .

· Нехай є операторним термом для бінарної функції . Утворимо функції та (обидві вони бінарні). Нехай є -східчастою функцією. Тоді є -східчастими функціями.

o Це випливає з двох нерівностей:

§

§

o Обидві вони доводяться математичною індукцією.

· Нехай , де - -арна функція, а - -арні. Тоді є -арною функцією.


Покажемо тепер, що існує ПРФ, яка не є елементарною.

Наприклад, візьмемо функцію . Для такої функції не існує такого єдиного , для якого можна було б мажорувати цю функцію -східчастою.


 







Date: 2015-09-24; view: 435; Нарушение авторских прав



mydocx.ru - 2015-2024 year. (0.005 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию