Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Співвідношення між класами примітивно рекурсивних та елементарних функцій
Нехай , де носій El – клас елементарних функцій; – це операції. Алфавіт: Визначення операторного терму: 1. Усі символи базових функцій є операторними термами. 2. Якщо є операторними термами для завдання m-арних функцій, а є термом для задання n-арної функції, то терм є термом для позначення m-арної функції. 3. Якщо є операторним термом для бінарної функції, то терми є операторними термами для бінарних функцій. 4. Інших оператор них термів не існує.
Для цього розглянемо допоміжну функцію : Функцію назвемо k -східчастою, якщо має місце умова: .
Доведення: · Базові функції: o o так само для ; o . · Нехай є операторним термом для бінарної функції . Утворимо функції та (обидві вони бінарні). Нехай є -східчастою функцією. Тоді є -східчастими функціями. o Це випливає з двох нерівностей: § § o Обидві вони доводяться математичною індукцією. · Нехай , де - -арна функція, а - -арні. Тоді є -арною функцією.
Наприклад, візьмемо функцію . Для такої функції не існує такого єдиного , для якого можна було б мажорувати цю функцію -східчастою.
Date: 2015-09-24; view: 422; Нарушение авторских прав |