Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Пример 7.2

Намерете стойността. S 3 ( I 2 2 , I 1 1 , 0 1 ). В този случай крайната функция ще бъде двуместна ( n = 3 - 1 = 2), следователно h ( x 1 , x 2 ) = I 2 2 ( I 1 1 , 0 1 ) = I 22 ( x 1 , 0) = 0.

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

Нека се дадат някои числени частични функции: n- седалка g (x 1 , ..., x n ) и (n + 2) -место h (x 1 , ..., x n , k, y). Казва се, че ( n + 1) -местната частична функция се формира от функции g и h чрез примитивна рекурсия, ако за всички естествени стойности на x f ; ..., x n , y е валидно:

Тъй като областта на дефиниране на функции е множеството на всички естествени числа, частичната функция f, отговаряща на условия (7.1), съществува за всяка частична функция g и h и тази функция ще бъде уникална. Условията (7.1) също определят последователността за определяне на стойностите на f при различни стъпки на рекурсия:

Символичната примитивна рекурсия се обозначава с f = R (g, h); в от този запис, R се счита за символ на частична операция на две места, определена на множеството от всички частични функции. Отношенията (7.2) предполагат по-специално, че ако g и h са навсякъде дефинирани, то f също е дефинирано навсякъде. От (7.2) се вижда също, че е важно, ако можем да намерим стойностите на функциите g и h, тогава стойностите на функцията f (a 1 , ..., a n , m + 1) могат да бъдат изчислени “механично” чрез намиране на последователно стойностите на предишната стъпки. Въвеждаме дефиницията.

Частичната функция f (x 1 , ..., x n ) се нарича примитивна рекурсивна, ако може да бъде получена от краен брой операции на суперпозиция и примитивна рекурсия, базирана само на най-простите функции S 1 , 0 n и I m n .

Ако операциите на суперпозиция и примитивна рекурсия се прилагат към дефинираните навсякъде функции, резултатът ще бъде и дефинирана навсякъде функция. По-специално, всички примитивни рекурсивни функции са дефинирани навсякъде.

Вижте също:

Всеки алгоритъм може да бъде дефиниран с помощта на функционална схема, изпълнена в съответната машина на Тюринг.

Ентропията на опита е равна на информацията, която получаваме в резултат на нейното изпълнение.

Нормални марковски алгоритми

Пример 9.3

Моделите се проверяват и не се проверяват

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru