Algoritm tushunchasi Tyuring mashinalari

A = {a₀ , a₁ , a₂ ,..., a_n ) Chekli simvollar jamlanmasi. A to'plam unsurlarining chekli ketma ketligi A to'plamtagi so'z deyiladi. So'zni tashkil qiluvchi simvollar soni o'sha so'zniń uzunligi deyiladi. Masalan, A alfavitning har bitta unsuri uzunligi 1 ge teng bo'lgan so'z dir. Bu alfavitte so'z ko'rinishinda mashinaga beriladigan axborot (informasiya) kodlastırıladı. Mashina so'z ko'rinishinda berilgan informasiyani takroriy ishlab, yangi so'z paydo qiladi.
2. Ichki alfavit, ya’nıy q₀ , q₁ , q₂ ,..., q_m P,L,N simvollar. q₀ , q₁ , q₂ ,..., q_m , - Mashinaning chekli son holatlarin bildiradi. Xohlagan mashinanıńjaǵdayları soni tayinlangan bo'ladi. Ikkita holatda maxsus vazifa bajariladi: q₁ - mashinanıng boshlang’ıch (dáslapki) holatı, q₀-natija (oxirgi)holati (toxtash holati ).
P, L, N - surilmoqlik simvollari dir (o'ngga, chapga va joyida ).
3. Ikkita tomonga cheksiz davom ettiruv mumkin bo'lgan lenta (mashinaning sirtqi xotirasi ). U katakchalarga (yacheykalarga) bo'lingan bo'ladi. Har bitta katakchaga xolos bitta xarf yozilishi mumkin. Bo’sh katakchani a₀ simvoli bilan belgilaymiz (1-formag’a qarang).

a0

a2

a3

a3

a7

a9

a11

a12

1-forma.
4. Boshqaruvchi kallak (golovka). U lenta bo'ylab harakat etadi va qandaydir katakcha (yacheyka) qarshisinda to'xtashi mumkin (2-forma ).

2-forma.
Bu holatda «kallak katakchani, ya'ni simvolni «kórib turibdi»» deb aytamiz. Mashinaning bitta takt davomidaǵI ishida kallak xolos bitta katakchaga surilishi (o'ngga, chapga ) yoki joyida turishi mumkin. Lentada saqlanayotgan har bitta informasiya sirtqi alfavitning a0 dan farqli chekli simvollar jamlanmasi bilan rasmlanadi. Mashina yumush boshlashinan oldin lentaga boshlang'ich axborot (boshlang'ich ma'lumot ) beriladi. Bu holda boshqaruvchi kallak, qoidaga asosan, q₁ boshlang’ısh
holatni ko'rsatuvchi oxirgi chap belgi qarshisinda turadi (3-forma
a₀ a₃ a₂ a₂ a₄ a₁


q₁ 3-forma.
Mashinaning ishi taktlar yig'indisidan iborat bo'lib, yumush davomida boshlang'ich informasiya masofa informasiyaga aylanadi.
Boshlang'ich informasiya sifatida lentaga sirtqi alfavitning katakchalarga xohlagan turda qo'yilgan chekli simvollar tizimini (alfavit dagi xohlagan so'zni ) berish mumkin. Berilgan boshlang'ich informasiyaga aloqador bo'lgan ikkita xil hol bo'lishi mumkin:
1. Mashina chekli san taktdan keyin toqtaydı (q₀₎ toqtap qalıw jag’dayına ótedi). Bu vaqtda lentada B informasiya rasmlangan bo'ladi. Bu holda mashina A boshlang'ich informasiyaga
qiyosan qo'llaniladigan (qollanib bo'lg'usi ) va uni takroriy ishlab B xotimalik informasiyaga keltirgan deb aytiladi
2. Mashina hech vaqt toqtamaydi, ya’nıy q₀ to’xtab qalısh holatidan otmaydi. Bu holda mashina A boshlang'ich informasiyaga qiyosan tatbiq etilmaydi deb aytiladi. Mashina ishiniing har bitta taktida quyidagi funksional sxema bo'yicha harakat etadi :

Bu yerda a_i , a_v – tashqi alifboning harflari; q _j , q_s- mashinaning holatlari; P, L, N –surilish simvollari .Basqarıwshı gellek lentada qanday harfni kórip turg’anlıg’ı (biziń jazıwda a_i

) hám mashina qaysı jag’dayda (biziń jazıwda q _j) turishganligiga qaray, bu taktda uchlar unsurten iborat komanda ishlab chiqiladi :
1) ko'rib turilgan xarf almashtirilgan sirtqi alfavit harfi a_;

2) Kelasi takt uchun sirtqi yod manzili

Kelasi takt manzili ( q_s).