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

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

Tyuring tezisi: Tyuring mashinasi algoritm tushunchasini aniqlashning bitta yo‘lini ko‘rsatadi. Shu tufayli bir necha savollar paydo bo‘ladi: - Tyuring mashinasi tushunchasi qancha umumiylik xususiyatiga ega? - algoritmlarni Tyuring mashinasi vositasi bilan berish usulini universal usul deb bo‘ladimi? - hamma algoritmlarni shu usul bilan berish mumkinmi? Bu savollarga hozirgi vaqtda mavjud bo‘lgan algoritmlar nazariyasi quyidagi gipoteza bilan javob beradi: har qanday algoritmni Tyuring funksional sxemasi orqali berish va mos Tyuring mashinasida realizatsiya etish (amalga oshirish) mumkin.

Bu gipoteza Tyuring tezisi deb ataladi. Uni isbotlash mumkin emas, chunki bu tezis qat’iy ta’riflanmagan algoritm tushunchasini qat’iy aniqlangan Tyuring mashinasi tushunchasi bilan bog'laydi. Bu tezisni rad etish uchun Tyuring mashinasida realizatsiya-lanmaydigan (amalga oshirilmaydigan) algoritm mavjudligini ko‘rsatish kerak. Ammo hozirgacha aniqlangan hamma algoritmlarni Tyuring funksional sxemasi orqali realizatsiya etish mumkin.