Makina Turing

Makina Turing është pajisje e thjeshtë që mund të simulojë logjikën e çfarëdo algoritmi kompjuterik dhe është shumë e dobishme për të shpjeguar punën e Njësisë Qëndrore të Procesimit brenda kompjuterit. Makina Turing punën e saj e kryen duke manipuluar me simbole sipër një shiriti që i mban ato simbole. Manipulimi bëhet sipas rregullave të caktuara.

Qëllimi

Një nga problemet themelore në filozofinë e shkencës kompjuterike është të përcaktohet se çka do të thotë nëse një detyrë është e llogaritshme. Nëse do të mund të përkufizohej një varg instruksionesh i quajtur procedurë efektive ose algoritëm, kryerja e të cilit nga një makinë do të kishte pasojë përfundimin e detyrës, do të mund të thonim që detyra përkatëse është e llogaritshme. Mirëpo nëse një procedurë funsionon për një makinë ajo prapë mund të mos funksionojë për një makinë tjetër, ose thënë ndryshe, bashkësia e instruksioneve që mund t’i kryejë një makinë varet nga aftësitë e asaj makine, dhe për pasojë do të mund të kemi klasë të ndryshme të detyrave të llogaritshme.

Në vitin 1936, shkencëtari anglez Alan Turing propozoi një klasë pajisjesh që do të njiheshin më vonë si makina Turing. Këto pajisje çuan në nocionin formal që do ta quajmë llogaritshmëri-Turing, sipas të cilit një detyrë është e llogaritshme nëse mund të kryhet nga një makinë Turing.

Detaje teknike

Makinat Turing janë pajisje llogaritëse të thjeshta abstrakte me anë të të cilave bëhen përpjekje për të ofruar një përgjigje për pyetjen “Çka mund të llogaritet?” Ato janë makina llogaritëse teorike që shërbejnë si një model i idealizuar për llogaritje matematike dhe nuk janë menduar që të shërbejnë si mjete praktike për llogaritje, por për të ndihmuar shkencëtarët të kuptojnë kufinjtë e llogaritjeve mekanike.

Ekzistojnë përkufizime të ndryshme të makinave Turing. Një prejt tyre përdor një shirit të pafundmë dykahësh, pesëshe të renditura dhe tri gjendje ndaluese, mirëpo të gjitha përkufizimet, përfshirë edhe atë që përmendëm, janë ekuivalente.

Për të dhënë përkufizime në lidhje me makinat Turing, do të përdoren këto tri bashkësi të ndara joboshe:

1) Bashkësia e fundme shirit ku B=a₀ është simboli zbraztë: A = {a1, a2, . . . , am} ∪ {B}

2) Bashkësia e fundme e gjendjeve ku s₀ është gjendja fillestare: S = {s1, s2, . . . , sn} ∪ {s0} ∪ {sH , sY , sN} ku sH (HALT) është gjendja ndaluese, sY (YES) është gjendja pranuese dhe sN (NO) është gjendja mospranuese

3) Bashkësia e kaheve ku L simbolizon majtë dhe R simbolizon djathtë: d = {L,R}

Një shprehje është një varg i fundmë (ndoshta i zbraztë) i elementeve nga A∪S∪d. Thënë ndryshe, një shprehje është një fjalë, simbolet e së cilës janë nga bashkësitë A, S dhe d.

Një shprehje e shiritit është një shprehje që përdor vetëm elementet e bashkësisë A.

Përshkrimi

Makina turing mund të shihet si një kokë lexuese/shkruese që lëviz para dhe prapa nëpër një shirit të pafundmë. Nëpër tërë gjatësinë e tij, shiriti është i ndarë në qeliza katrore dhe secila prej qelizave mund të jetë e zbraztë ose të mbajë një simbol shiriti. Në rastin kur qeliza është e zbraztë, mund të thuhet se ajo mban simbolin zbraztë. Në secilin hap makina Turing M është në një gjendje të caktuar si dhe duke lexuar njërin nga simbolet e shiritit aj në shirit. Supozimin që shiriti mban vetëm një numër të fundmë simbolesh e marrim si të vërtetë.

Figura 1(a) është një pamje e një makine Turing M në gjendjen s2 teksa lexon simbolin e dytë me ç’rast në shirit shtypet a1a3Ba1a1 (B është simboli zbraztë). Kjo pamje mund të paraqitet me shprehjen α = a1s2a3Ba1a1 ku gjendjen s2 të M e shkruajmë para simbolit në shirit a3 të cilin është duke e lexuar M. Vëreni që α është një shprehje që përdor vetëm alfabetin e shirit A, përveq simbolit të gjendjes s2 i cili nuk është në fund të shprehjes pasiqë shfaqet para simbolit të shiritit a3 të cilin është duke e lexuar M. Figura 1 tregon dy pamje të tjera joformale dhe shprehjet e pamjeve përkatëse.

(Figura 1) Gjendje të ndryshme të makinave Turing

Një pamje α është një shprehje si ajo e dhënë në vazhdim ku P dhe Q janë shprehje të shiritit (që mund të jenë të zbrazta): α = PsiakQ

Le të jetë α = PsiakQ një pamje. Themi se makina Turing M është në gjendjen si duke lexuar shkronjën ak dhe se shprehja në shirit është shprehja PakQ, pra pa simbolin e gjendjes si.

Siq u tha më lartë, në çdo hap në kohë, makina Turing M është në një gjendje të caktuar si dhe duke e lexuar një simbol në shirit ak.

Makina Turing M është në gjendje t’i kryejë të tre veprimet në vazhdim në të njëjtën kohë: i) M fshin simbolin ak dhe në vend të tij shkruan simbolin e shiritit al (ku lejohet al = ak). ii) M ndërron gjendjen e vet të brendshme si në një gjendje sj (ku lejohet sj = si). iii) M lëviz për një qelizë në të djathtë ose për një qelizë në të majtë.

Veprimi i mësipërm nga M mund të përshkruhet me anë të një shprehjeje me pesë shkronja që quhet pesëshe e renditur të cilën e përkufizojmë më poshtë.

Një pesëshe e renditur q është një shprehje me pesë shkronja e formës së mëposhtme:

Pesëshja e renditur që përkufizon një Makinë Turing

Pra, shkronja e parë e q është simboli i gjendjes, shkronja e dytë është simbol i shiritit, shkronja e tretë është është simbol i shiritit, shkronja e katërt është simbol i gjendjes dhe shkronja e fundit është simbol i kahut L ose R.

Tani do të japim një përkufizim formal të një makine Turing.

Një makinë Turing M është bashkësi a fundme e pesësheve të renditura të tilla që: (i) Nuk ekzistojnë dy pesëshe të renditura që i kanë dy shkronjat e para të njëjta. (ii) Asnjë pesëshe e renditur nuk fillon me sH, sY ose sN.

Kushti (i) në përkufizim na garanton që makina M nuk mund të kryejë më shumë se një veprim në cilindo hap dhe kushti (ii) na garanton që makina M ndalon në gjendjen sH, sY ose sN.

Krahasimi me makinat e vërteta

Shpesh thuhet se për dallim nga automatet e thjeshtë, makinat Turing janë po aq të fuqishme sa makinat e vërteta, mirëpo “makinat e vërteta” në fakt janë vetëm automate me një numër të fundmë konfigurimesh, përderisa makinat Turing janë ekuivalente me makinat që kanë sasi të pafundme të hapësirës për të ruajtur të dhëna gjatë llogaritjeve. Për më tepër, qëllimi i makinave Turing nuk është që të modelojnë makinat të cilat i bëjnë llogaritjet por që të modelojnë vetë llogaritjet. Ja disa arsye pse makinat Turing janë modele të dobishme të kompjuterëve të vërtetë:

1. Çdo gjë që mund të llogaritet nga një kompjuter i vërtetë mund të llogaritet edhe nga një makinë Turing.
2. Dallimi qëndron tek aftësia e makinës Turing për të manipuluar sasi të pakufizuar të dhënash edhe pse për një kohë të fundme.
3. Njëjtë si një makine Turing, edhe një makine të vërtetë mund t’i zgjerohet hapësira ruajtëse sipas nevojës. Pra, asnjërës makinë nuk i duhet sasi shumë e madhe e hapësirës ruajtëse për të kryer llogaritje të dobishme.

Një gjë që i bën makinat Turing modele më të dobëta për programe është fakti se shumë programe të vërteta siq janë sistemet operative janë të shkruar në mënyrë të tillë që të marrin input të pakufizuar mbi kohë, prandaj nuk ndalojnë. Makinat Turing nuk i modelojnë mirë llogaritjet e tilla që vazhdojnë, edhe pse mund të modelojnë pjesë të këtyre llogaritjeve.

Burime

• Computer viruses: from theory to applications 3, Eric Filiol
• Discrete Mathematics, Seymour Lipschutz, Marc Lars Lipson
• Discrete Mathematics and its applications, Kenneth H. Rosen
• Artikull nga faqja Wolfram mathworld
• Artikull nga encikolpedia Stanford