Makina Turing: Dallime mes rishikimesh

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

 

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):