logo

Tyuring mashinasida hisoblash

Загружено в:

10.08.2023

Скачано:

0

Размер:

311.4072265625 KB
Ty uring mashinasida 
hisoblash  
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. 
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 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. 
MEXANIZM QANDAY ISHLAYDI

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. 
MEX AN IZM X USUSIYATLARI

Tyuring mashinasi, boshqa hisoblash tizimlari kabi, o'ziga xos 
xususiyatlarga ega va ular algoritmlarning xususiyatlariga 
o'xshaydi:

Diskretlik. Raqamli mashina keyingi bosqichga o'tadi n + 1 
oldingisi tugagandan keyingina. Har bir tugallangan bosqich n 
+ 1 bo'lishini belgilaydi.

Tushunuvchanlik. Qurilma bir xil hujayra uchun faqat bitta 
amalni bajaradi. U alifbodagi belgini yozadi va bitta harakatni 
amalga oshiradi: chap yoki o'ng.

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.

Samaradorlik. Har bir bosqich uchun aniq natija Turing 
mashinasi tomonidan aniqlanadi. Dastur algoritmni bajaradi va 
cheklangan miqdordagi qadamlarda q0 holatiga o'tadi.

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. 
QURI LMA 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. HI SOBLA SH KOMPON EN TLA RI

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.

Ty uring mashinasida hisoblash

 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.

 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 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.