Студопедия
Обратная связь


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram 500-летие Реформации


Пример 7.2

Найти значение. S3(I22, I11,01). В этом случае конечная функция будет двуместной (п = 3 - 1 = 2), следовательно h(х1, х2) = I22(I11, 01) = I22(x1, 0) = 0 .

Примитивная рекурсия

Пусть заданы какие-либо числовые частичные функции: n-местная g(x1,..., хn) и (п + 2)-местная h(x1, ..., xn, k, у). Говорят, что (п + 1)-местная частичная функция f образуется из функций д и h посредством примитивной рекурсии, если для всех натуральных значений х1;..., xn, у справедливо:

Поскольку областью определения функций является множество всех натуральных чисел, частичная функция f, удовлетворяющая условиям (7.1), существует для каждых частичных функций g и h и функция эта будет единственной. Условия (7.1) задают также последовательность определения значений f на различных шагах рекурсии:

Символически примитивная рекурсия обозначается f = R(g,h); в этой записи R рассматривается как символ двуместной частичной операции, определенной на множестве всех частичных функций. Из соотношений (7.2) вытекает, в частности, что если g и h являются всюду определенными, то и f также является всюду определенной. Из (7.2) видно также то важное обстоятельство, что если умеем находить значения функций g и h, то значения функции f(a1,..., an, т + 1) можно вычислять «механически», находя последовательно значения на предыдущих шагах. Введем определение.

Частичная функция f(x1,..., xn) называется примитивно рекурсивной, если ее можно получить конечным числом операций суперпозиции и примитивной рекурсии, исходя лишь из простейших функций S1, 0n и Imn.

Если операции суперпозиции и примитивной рекурсии применить к всюду определенным функциям, в результате будет получена также всюду определенная функция. В частности, все примитивно рекурсивные функции всюду определены.

 

Читайте также:

Блочное двоичное кодирование

Пример А.3

Организация структур данных в ОЗУ

Постановка задачи

Глоссарий

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1465

 
 

© studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам. Ваш ip: 54.196.91.84