3-4-mavzu: Primitiv rekursiv funksiyalar. Tyuring tezisi. Markovning normal algoritmi

Informatika kafedrasi o’qituvchisi Elbek Abduqodirovning Primitiv rekursiv funksiyalar. Tyuring tezisi. Markovning normal algoritmi. mavzusiga tayyorlagan TAQDIMOTI

3-4-MAVZU: Primitiv rekursiv funksiyalar. Tyuring tezisi. Markovning normal algoritmi.

• REJA:
• 1. Primitiv rekursiv funksiyalar.
• 2. Tyuring tezisi.
• 3. Markovning normal algoritmi.

Foydalanilgan adabiyotlar.

• 1. Горбатов В.А., Останков Б.Л., Фролов С.А . Регулярные структуры автоматного управления / Под ред. В .А .Горбатова . М., «Машиностроение», 1980.
• 2. Горбатов В.А., Павлов П .Г ., Четвериков В.Н. Логическое управление информационными процессами. М., « Энергоатомиздат », 1984.
• 3. Гроссман И., Магнус В. Группы и графы. М ., «Мир», 1971.
• 4. Дорофеев Г. В., П о тап о в М . К., Розов Н. X. Пособие по математики для поступаю щ их в вузы. М., «Наука», 1976.
• 5. Евстигнеев В. А. Применение теории графов в программировании. М., «Наука», 1985.
• 6. Ерусалимски й Я. М. Дискретная математика: теория, задачи, приложения. М., «Вузовская книга», 2000

Primitiv rekursiv funksiyalar.

• Agar f (, , …, ) funksiyani boshlang’ich (oddiy) funksiyalardan superpozitsiya va primitive rekursiya sxemasi amallarini chekli son marta qo’llash natijasida hosil qilish mumkin bo’lsa, u holda f (, , …, ) primitiv rekursiv funksiya deb ataladi.

•  

Masalan: boshlang’ich 0 (x) = 0, l (x) = x+1, (x1, y2, …, xn)=xm (1mn) funksiyalar va f (x1, x2, … , xn) =a. (aN), f(x, y) = x+y, f(x, y) =x*y, f(x, y) = () funksiyalar primitiv rekursiv funksiyalar bo’ladi.

Agar f (x1, x2, … , xn) funksiyaning boshlang’ich funksiyalardan superpozitsiya, primitiv rekursiya sxemasi va minimallash operatori (m-operatori) amallarini chekli son marta qo'llash natijasida hosil etish mumkin bo'lsa, u holda f (x1, x2, … , xn) qismiy rekursiv funksiya deb ataladi.

• Agar f (x1, x2, … , xn) funksiyaning boshlang’ich funksiyalardan superpozitsiya, primitiv rekursiya sxemasi va minimallash operatori (m-operatori) amallarini chekli son marta qo'llash natijasida hosil etish mumkin bo'lsa, u holda f (x1, x2, … , xn) qismiy rekursiv funksiya deb ataladi.
• Primitiv rekursiv funksiyaning ta’rifidan faqat boshlang'ich funksiyalarga qo'shimcha ravishda m -operatorini qo'llashga ruxsat berilishi bilan farq qiladi. Shuning uchun ham har qanday primitiv rekursiv funksiya о‘z navbatida qismiy rekursiv funksiya bo‘ladi.