Pagkakaiba sa mga pagbabagong ng "Makinang Turing"

m
walang buod ng pagbabago
m
Ang '''makinang Turing''' (sa Ingles ay '''Turing machine''') ay isang [[teoretikal]] na kasangkapan na nagmamanipula ng mga simbolo sa isang mahabang piraso ng [[tape]] ayon sa tabla ng mga patakaran. Bagaman ito ay may kasimplehan, ang isang makinang Turing ay maaaring baguhin upang tularan(simulate) ang [[lohika]] ng anumang [[algoritmo]] ng [[kompyuter]] at ito ay partikular na magagamit sa pagpapaliwanag ng mga tungkulin ng [[CPU]] sa loob ng kompyuter.
 
Ang makinang Turing ay inilarawan ni [[Alan Turing]] noong 1936 na tumawag ditong "a(utomatic)-machine". Ang makinang Turing ay hindi nilalayon bilang praktikal na teknolohiyang pang-kwenta ngunit bilang isang [[eksperimento ng pag-iisip]] sa kumakatawan sa isang makinang kumu-kwenta. Ang mga makinang Turing ay nakakatulong sa mga siyentipiko ng kompyuter upang maunawaan ang limitasyon ng pagku-kwentang mekanikal.
Sa mas tiyak na kahulugan, ang makinang Turing ay binubuo ng:
<ol>
<li>Isang tape na hinati sa mga selula(cell) na magkakasunod. Ang bawat selula ay naglalaman ng simbolo mula sa isang may hangganang alpabeto. Ang alpabeto ay naglalaman ng isang espesyal na blankong simbolo(dito ay isinusulat bilang 'B') at isa o maraming mga iba pang simbolo. Ang tape ay ipinagpapalagay na arbitraryong mapapalawak sa kaliwa at sa kanan o nangangahuluangnangangahulugang ang makinang Turing ay palaging sinusuplayan ng maraming tape na kailangan nito sa pagkwenta. Ang mga selula na hindi pa nasusulatan ay pinagpapalagay na naglalaman ng simbolong blanko. Sa ilang mga modelo, ang tape ay may kaliwang dulo na minarkhan ng isang espesyal na simbolo; ang tape ay lumalawig o walang hanggang mapapahaba sa kanan. </li>
<li>Ang ulo na makakabasa at makakasulat ng mga simbolo sa tape at lumilipat sa kaliwa o kanan ng tape na isa isa. Sa ilang mga modelo, ang ulo ay lumilipat at ang tape ay hindi gumagalaw. </li>
<li>Ang isang may hangganang tabla(na minsang tinatawag na tabla ng aksiyon o punsiyong transisyon) ng mga instruksiyon(na karaniwan ay kwintuple[5-tuple] : q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub> ngunit minsan ay 4-tuple) na kung ibinigay ang estadong(qi) na kasalukuyang estado ng makina at ang simbolong (a<sub>j</sub>) kasalakuyang binabasa sa tape ay nagsasabi sa makina na isagawa ang sumusunod na sekwensiya(para sa mga modelong 5-tuple):