MühaziRƏ 1 Verilənlər. Alqoritmlər və verilənlərin strukturu

Tyurinq maşınlarının formal olmayan tərifi

Tyurinq maşını hər iki tərəfə uzadılmış lenti olan avtomatdan ibarətdir:hesablayıcı başlıq və idarəedici qurğu .

İdarəedici qurğu Q={q₀,q₁,...,q_n} sonlu çoxluğu əmələ gətirən vəziyyətlərdən birində ola bilər.Q çoxluğunu Tyurinq maşınının daxili əlifbası da adlandırırlar.

Tyurinq maşınının hesablama maşınlarından prinsipial fərqi ondan ibarətdir ki,onun yaddaş qurğusu sonsuz lent şəklində olur və onun fiziki realizasiyası mümkün deyil.Lent yuvalara(xanalara) bölünmüşdür və hər bir yuvada A={a₀,a₁,...,a_m} sonlu əlifbasının simvollarından biri yazılır.A əlifbası Tyurinq maşınının giriş əlifbası adlandırılır.Tyurinq maşınının fəaliyyəti zamanı sonlu sayda yuvalar doldurula bilər.Hesablayıcı başlıq hər bir zaman anında lentin yuvasında olan simvoldan asılı olaraq ,onu təsvir edir.İdarəedici qurğu bu yuvaya (xanaya) ya yeni simvol yazır ya da onu sağa və ya sola sürüşdürməklə dəyişməz saxlayır ya da köhnə yerində saxlayır.Bu zaman idarəedici qurğu ya yeni vəziyyətə keçir ya da əvvəlki vəziyyətdə qalır .İdarəedici qurğunun vəziyyətləri arasında q₀ ilkin vəziyyəti və q_n son vəziyyəti xüsusi olaraq qeyd olunur.

Beləliklə,Tyurinq maşını bir takt ərzində simvolu oxuyaraq ,ya onun yerinə yeni simvol yazır, ya onu dəyişməz saxlayaraq başlığı bir xana sağa ya sola sürüşdürür, ya da onu öz yerində saxlayır.