Hozirgi kunda biror bir sohada ishni boshlash va uni boshqarishni kompyutersiz tasavvur qilish qiyin. XXI asr savodxon kishisi bo’lishi uchun kompyuter savodxon bo’lish, axborot texnologiyalarini puxta egallamoq lozim

15 - MAVZU: TYURING MASHINASI


Reja


1. Tyuring mashinasining yaratilish tarixi.
2. Tyuring mashinasi algoritmi ishlash prinsipi.
3. Tyuring mashinasi algoritmi imkoniyatlari

Tyuring mashinasi – bu 1936 yilda ingliz olimi A. Tyuring tomonidan universal algoritmik model sifatida taklif qilingan abstrakt mashina. U uch qismdan iborat: lenta, golovka va boshqaruv qurilma (rasm 1).

Lenta ikki tomonga cheksiz uzun va katakchalarga bo’lingan. Har bir katakchada faqat bitta belgi yoziladi. Mumkin bo’lgan simvollar soni chekliva mashinaning deb belgilangan alfavitni tashkil qiladi. Simvol yo’qligi maxsus bo’sliq belgisi bilan ko’rsatiladi.
Golovka hamma vaqt lentaning biror-bir katakchasi ustida joylashgan bo’ladi. U katakchalarni o’qiydi, yozadi, o’chiradi va lenta bo’ylab yurishi mumkin. Golovka har bir ish siklida chekli to’plamga tegishli holatlardan birida bo’ladi. Holatlar ichidan - boshlang’ich va -yakuniy holatlarni ajratib ko’rsatishi mumkin.
Tyuring mashinasining bir elementar qadami quyidagilardan iborat. Golovka qaysi yacheyka ustida joylashgan bo’lsa, shunga yozilgan simvolni o’qiydi. Simvol qiymati va o’zining holatidan kelib chiqib, golovka yangi holatga o’tadi va qaysi simvolni yozish va qanaqa harakatni bajarish ko’rsatilgan komandani amalga oshiradi. Shunday qilib, mashina keyingi qadamni bajarishga tayyor.
Mashina ishlaydigan qoidani quyidagicha ko’rsatish mumkin: . Bu yerda -har xil holatlar, -o’qiladigan va yoziladigan simvollar, -golovkaning harakati. Bu hharakat uch xil bo’lishi mumkin: bir katakcha chapga, bir katak o’ngga, joyida qolish. Har bir kombinatsiyasi uchun faqat bitta qoida ishlaydi. Lekin uchun qoida yo’q, chunki mashina to’xtaydi.
Konkret Tyuring mashinasi A va Q elementlarini hamda qoidalar to’plamini belgilash bilan beriladi. A, Q to’plamlar va qoidalarhillari cheksiz ko’p bo’lishi mumkin, shu sababli konkret Tyuring mashinalari ham cheksiz ko’p bo’lishlari mumkin.
Qoidalar to’plami odatda jadval ko’rinisida beriladi. Satrlar bo’yicha holatlar, ustunlarga simvollar qo’yiladi. satri va ustuni kesishmasida esa uchta belgi qo’yiladi. Har bir bo’sh bo’lmagan jadval katakchasiga qandaydir qoida mos keladi, bo’sh katakcha esa qoida yo’qligi va keraksizligini ko’rsatadi, chunki bu holatda golovka hech qachon simvolga uchramaydi.
Tyuring mashinasi yordamida xilma-xil turdagi funksiyalarni hisoblash mumkin: sonli,.mantiqiy, simvolli. Funksiyani turi, odatdagidek, kirish va chiqish ma’lumotlari bilan belgilanadi. Umuman Tyuring tezligi bo’yicha ixtiyoriy isoblanadigan funksiyaga (agar uni hisoblaydigan algoritm mavjud bo’lsa) Tyuring mashinasini ko’rish va qo’llash mumkin.