Makinang Turing: Pagkakaiba sa mga binago
Content deleted Content added
mNo edit summary |
|||
Linya 1:
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.
Linya 14:
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
<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):
| |||