Makina Turing: Dallime mes rishikimesh
| [Redaktim i kontrolluar] | [Redaktim i kontrolluar] |
Content deleted Content added
No edit summary |
Marbott (diskuto | kontribute) v Rregullim i sintaksës using AWB |
||
Rreshti 4:
Një nga problemet themelore në filozofinë e [[Shkenca kompjuterike|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.
Rreshti 33:
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.
[[Skeda:Figura 1(Makina Turing).PNG|thumb|700px|center|(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):
Line 68 ⟶ 63:
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
Line 85 ⟶ 79:
* {{en}} [http://mathworld.wolfram.com/TuringMachine.html Artikull nga faqja Wolfram mathworld]
* {{en}} [http://plato.stanford.edu/entries/turing-machine/ Artikull nga encikolpedia Stanford]
[[Kategoria:Kompjuterikë]]▼
{{tek-cung}}
▲[[Kategoria:Kompjuterikë]]
| |||