Tyuring mashinasi

TYURING MASHINASI
REJA:

1. 
   Tyuring mashinasi yaratilishi tarixi
   
2. 
   Tyuring mashinasi tuzilishi
   
3. 
   Qurilma dasturi
   
4. 
   Tyuring mashinasi: misollar
   

Tyuring mashinasi 20-asrning eng qiziqarli va hayajonli intellektual kashfiyotlaridan biridir. Bu hisoblashning oddiy va foydali mavhum modeli (kompyuter va raqamli) bo'lib, har qanday kompyuter vazifasini amalga oshirish uchun etarlicha umumiydir. Rahmat oddiy tavsif va matematik tahlilni amalga oshirib, nazariy informatikaning asosini tashkil qiladi. Ushbu tadqiqot raqamli kompyuterlar va hisob-kitoblarni chuqurroq tushunishga olib keldi, jumladan, umumiy foydalanuvchi kompyuterlarida hal etilmaydigan ba'zi hisoblash muammolari mavjudligini tushunish.

Alan Turing kompyuter bilan bir xil asosiy imkoniyatlarga ega bo'lgan mexanik qurilmaning eng ibtidoiy modelini tasvirlashga harakat qildi. Turing mashinani birinchi marta 1936 yilda London Matematik Jamiyati materiallarida chop etilgan "Hisoblash mumkin bo'lgan sonlar to'g'risida" gi masalani yechish muammosi bilan ta'riflagan.
Turing mashinasi - bu o'qish / yozish kallagidan (yoki "skaner") iborat bo'lgan hisoblash qurilmasi bo'lib, u orqali qog'oz tasmasi o'tadi. Lenta kvadratlarga bo'lingan, ularning har biri bitta belgi - "0" yoki "1". Mexanizmning maqsadi shundan iboratki, u ham kirish va chiqish vositasi, ham hisob-kitoblarning oraliq bosqichlari natijalarini saqlash uchun ishchi xotira sifatida ishlaydi.
Har bir bunday mashina ikkita komponentdan iborat:

1. 
   Cheksiz tasma. U har ikki yo'nalishda ham cheksiz bo'lib, hujayralarga bo'linadi.
   
2. 
   Avtomatik mashina - boshqariladigan dastur, ma'lumotlarni o'qish va yozish uchun bosh-skaner. Bu har qanday vaqtda ko'plab shtatlardan birida bo'lishi mumkin.
   

Har bir mashina ikkita chekli ma'lumotlar qatorini bog'laydi: kiruvchi belgilar alifbosi A = (a0, a1, ..., am) va holatlar alifbosi Q = (q0, q1, ..., qp). q0 holati passiv deb ataladi. Taxminlarga ko'ra, qurilma urilganda o'z ishini tugatadi. q1 holati boshlang'ich holat deb ataladi - mashina o'z hisob-kitoblarini uning boshida bo'lgan holda boshlaydi. Kirish so'zi lentada joylashgan bo'lib, har bir pozitsiyada bir qatorda bitta harf. Uning ikkala tomonida faqat bo'sh hujayralar joylashgan.
Turing mashinasi hisoblash qurilmalaridan tubdan farq qiladi - uning xotira qurilmasi cheksiz lentaga ega, raqamli qurilmalarda esa bunday qurilma ma'lum uzunlikdagi chiziqqa ega. Har bir vazifa sinfi faqat bitta qurilgan Turing mashinasi tomonidan hal qilinadi. Boshqa turdagi muammolar yangi algoritm yozishni o'z ichiga oladi.
Tekshirish moslamasi bitta holatda bo'lib, kamar bo'ylab istalgan yo'nalishda harakatlanishi mumkin. U chekli alifboning belgilarini hujayralarga yozadi va o'qiydi. Harakat paytida bo'sh element tanlanadi, u kirish ma'lumotlarini o'z ichiga olmaydigan pozitsiyalarni to'ldiradi. Turing mashinasi algoritmi boshqaruv qurilmasi uchun o'tish qoidalarini belgilaydi. Ular o'qish-yozish boshiga quyidagi parametrlarni o'rnatadilar: katakka yangi belgi yozish, yangi holatga o'tish, lenta bo'ylab chapga yoki o'ngga siljitish.

MEXANIZM XUSUSIYATLARI
Tyuring mashinasi, boshqa hisoblash tizimlari kabi, o'ziga xos xususiyatlarga ega va ular algoritmlarning xususiyatlariga o'xshaydi:

1. 
   Diskretlik. Raqamli mashina keyingi bosqichga o'tadi n + 1 oldingisi tugagandan keyingina. Har bir tugallangan bosqich n + 1 bo'lishini belgilaydi.
   
2. 
   Tushunuvchanlik. Qurilma bir xil hujayra uchun faqat bitta amalni bajaradi. U alifbodagi belgini yozadi va bitta harakatni amalga oshiradi: chap yoki o'ng.
   
3. 
   Determinizm. Mexanizmdagi har bir pozitsiya ma'lum bir sxemani bajarishning yagona variantiga mos keladi va har bir bosqichda harakatlar va ularni amalga oshirish ketma-ketligi aniq.
   
4. 
   Samaradorlik. Har bir bosqich uchun aniq natija Turing mashinasi tomonidan aniqlanadi. Dastur algoritmni bajaradi va cheklangan miqdordagi qadamlarda q0 holatiga o'tadi.
   
5. 
   Ommaviy xarakter. Har bir qurilma to'g'ri alifbo so'zlari bo'yicha aniqlanadi.
   

TYURING MASHINASINING VAZIFALARI
Algoritmlarni echishda ko'pincha funktsiyani amalga oshirish talab qilinadi. Hisoblash uchun zanjirni yozish imkoniyatiga qarab, funktsiya algoritmik hal qilinadigan yoki hal etilmaydigan deb ataladi. Tabiiy yoki ratsional sonlar to'plami sifatida, mashina uchun chekli N alifbosidagi so'zlar, biz B to'plamining ketma-ketligini ko'rib chiqamiz - B = (0,1) ikkilik kod alifbosi doirasidagi so'zlar. Shuningdek, hisoblash natijasi algoritm "osilib qolganda" yuzaga keladigan "aniqlanmagan" qiymatni hisobga oladi. Funktsiyani amalga oshirish uchun rasmiy tilning cheklangan alifboda mavjudligi va to'g'ri tavsiflarni tanib olish muammosi hal qilinishi muhimdir.

QURILMA DASTURI
Turing mexanizmi uchun dasturlar jadvallar bilan formatlangan bo'lib, unda birinchi qator va ustun tashqi alifbo belgilarini va mashinaning mumkin bo'lgan ichki holatining qiymatlarini - ichki alifboni o'z ichiga oladi. Jadvalli ma'lumotlar Turing mashinasi tomonidan qabul qilinadigan buyruqlardir. Muammolarning yechimi quyidagicha: hujayradagi bosh tomonidan o'qilgan xat, u yuqorida joylashgan bu daqiqa topiladi va mashina boshining ichki holati buyruqlarning qaysi biri bajarilishi kerakligini belgilaydi. Xususan, bunday buyruq jadvaldagi tashqi va ichki alifbo belgilarining kesishgan joyida joylashgan.

HISOBLASH KOMPONENTLARI
Bitta aniq muammoni hal qilish uchun Tyuring mashinasini qurish uchun uning quyidagi parametrlarini aniqlash kerak.
Tashqi alifbo. Bu A belgisi bilan belgilanadigan, tashkil etuvchi elementlari harflar bilan ataladigan ba'zi chekli belgilar to'plami. Ulardan biri - a0 - bo'sh bo'lishi kerak. Masalan, Tyuring qurilmasi bilan ishlaydigan alifbo ikkilik raqamlar, quyidagicha ko'rinadi: A = (0, 1, a0).
Lentaga yozib olingan harf-ramzlarning uzilmagan qatori so'z deyiladi.
Avtomat - bu inson aralashuvisiz ishlaydigan qurilma. Turing mashinasida u muammolarni hal qilish uchun bir necha xil holatlarga ega va yuzaga keladigan muayyan sharoitlarda bir pozitsiyadan ikkinchisiga o'tadi. Bunday tashish holatlarining to'plami ichki alifbodir. U Q = (q1, q2 ...) ko'rinishidagi harf belgisiga ega. Ushbu pozitsiyalardan biri - q1 - boshlang'ich bo'lishi kerak, ya'ni dasturni ishga tushiradigan narsa. Yana bir zarur element - bu yakuniy, ya'ni dasturni tugatuvchi va qurilmani to'xtash holatiga keltiradigan holat q0.
O'tish stoli. Ushbu komponent mashinaning holati va hozirgi vaqtda o'qilayotgan belgining qiymatiga qarab, qurilma vagonining xatti-harakati uchun algoritmdir.

AVTOMAT UCHUN ALGORITM
Turing qurilmasining ish paytida tashish dasturi har bir bosqichda quyidagi harakatlar ketma-ketligini bajaradigan dastur tomonidan boshqariladi:

1. 
   Tashqi alifbo belgisini pozitsiyaga, shu jumladan bo'shga yozish, undagi elementni, shu jumladan bo'shni almashtirish.
   
2. 
   Bir katakchani chapga yoki o'ngga siljiting.
   
3. 
   Sizning ichki holatingizni o'zgartirish.
   

Shunday qilib, har bir juft belgilar yoki pozitsiyalar uchun dasturlarni yozishda uchta parametrni aniq tasvirlash kerak: ai - tanlangan A alifbosidan element, vagonning siljish yo'nalishi ("←" chapga, "→" o'ng, "nuqta" - harakat yo'q) va qk - qurilmaning yangi holati Masalan, 1 "←" q 2 buyrug'i "belgini 1 ga almashtiring, vagon boshini chapga bir katak qadamiga o'tkazing va bajaring. q 2" holatiga o'tish.
TYURING MASHINASI: MISOLLAR