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.