Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Функції, елементарні за Кальмаром
Функція f(х,у) отримується з функції g(х,у) за допомогою операції сумування, якщо для всіх х, у є N маємо . Функція f(х,у) отримується з функції g(х,у) за допомогою операції мультиплікації, якщо для всіх х, у є N маємо . Функція f(x1,..., xn) елементарнa (елементарнa за Кальмаром), якщо вона може бути отримана з функцій s, I , + та за допомогою скінченної кількості застосувань операцій суперпозиції, сумування і мультиплікації. Наступні співвідношення встановлюють елементарність відомих функцій: 1) о (x) = х х; 2) ; 3) (х) = s (о (х)); 4) = 5) sg(x) = x (х 1); 6) nsg(x) = 1 (х) х; 8) mod(х, у) = х (у х / у]) 9)C(x, y)=[((x+y)2 + 3*x+y)/2]; 10) x! =x∏i=1 i 11) xy=y∏ i=1 I21(x,i).
Тоді f(х) – елементарна функція, якщо функції gi(x), αi(x), де 1£ i £n, елементарні.
Звідси f(х) елементарна функція, якщо функції g(х,у) та α(x) елементарні. Кажуть, що функція f(х,у) отримується за допомогою операції обмеженої рекурсії з функцій g(х), h(х, у, z) та φ(х, у), якщо: 1) функція f(х, у) задається схемою примітивної рекурсії f(х, 0) = g(х), f(х, у) = h(х, у 1), f(х, у 1)), 2) для всіх х, у є N маємо f(х, у)£φ (х, у).
Визначимо операцію обмеженої рекурсії в загальному випадку. Нагадаємо, що є скороченим позначенням послідовності x1,..., xn Скажемо, що функція f(, у) отримана за допомогою операції обмеженої рекурсії з функцій g(), h(, у, z) та φ(, у), якщо вона задана схемою примітивної рекурсії f(, 0) = g(), f(, у) = h(,у 1), f(,у 1)), причому для всіх єNn та уєN маємо f(, у) £ φ(, у). Має місце природне узагальнення теореми 9.1.1. Теорема. Нехай функція f(, у) отримана за допомогою операції обмеженої рекурсії з елементарних функцій g(), h(, у, z) та φ(, у). Тоді функція f(, у) також елементарна.
Date: 2015-09-24; view: 385; Нарушение авторских прав |