Makinang Turing

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.

Si Turing ay nagbigay ng sapat na maikling depinisyon ng eksperimento sa kanyang sanaysay noong 1948 na pinamagatang "Intelihenteng Makinarya(Intelligent Machinery)". Sa pagtukoy sa kanyang akda noong 1936, isinulat ni Turing na ang makinang Turing na tinatawag ditong "Lohikal na Nagkukwentang Makina(Logical Computing Machine)" ay binubuo ng:

...walang hanggang kakayahan ng memorya na makakamit sa anyong ng isang walang hanggang tape na minarkhan bilang mga parisukat na sa bawat isa ay maaaring tatakan ng isang simbolo. Sa anumang pagkakataon, meron lamang isang simbolo sa makina na tinatawag na binasang(scanned) simbolo. Maaaring baguhin ng makina ang binasang simbol at ang pag-aasal nito ay sa isang bahagi matutukoy ng simbolong ito ngunit ang mga simbolo sa tape sa iba pang lugar ay hindi nakakaapekto sa pag-aasal ng makina. Gayunpaman, ang tape ay maaaring muling pabalikin at pasulungin sa makina na ito isa sa mga pangunahing operasyon ng makina. Kaya ang anumang simbolo sa tape ay sa kalaunan may pagkakataon(innings). (Turing 1948, p. 61)

Ang isang makinang Turing na may kakayahang gumaya sa anumang iba pang makinang Turing ay tinatwag na pangkalahatang makinang Turing(Turing machine o UTM o universal machine). Ang isang mas matematikal na depinisyon na may kaparehong "pangkalahatan(unibersal)" na kalikasan ay ipinakilala ni Alonzo Church na ang kanyang akda sa kalkulong lambda ay kaugnay ng gawa ni TUring sa isang pormal na teoriya ng komputasyon na kilala bilang tesis na Church-Turing. Ang tesis na ito ay nagsasaad na ang mga makinang Turing ay talagang nabibihag ang inpormal na nosyon ng epektibong paraan sa lohika at matematika at nagbibigay ng tiyak na depinisyon ng algoritmo o mekanikal na hakbang. Ang pag-aaral ng mga abstraktong katangian nito ay nagbibigay ng maaraming mga pagkaunawa sa agham pangkompyuter at teorya ng komputasyonal na komplehidad.