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.

Impormal na depinisyon

Matematikal na namomodelo ng makinang Turing ang isang makina na mekanikal na nagsasagawa ng operasyon sa isang tape. Sa tape na ito ang mga simbolo na maaaring basahin at isulat ng makina na isa isa gamit ang ulo ng tape. Ang operasyon ay buong matutukoy ng may hangganang pangkat ng mga elementaryong instruksiyon gaya ng "sa estadong 42, kung ang simbolo ay nababasang 0, isulat ang 1; kung ang simbolo ay nababasang 1, lumipat sa kanan at magbago sa estadong 17; sa estadong 17, kung ang simbolo ay nababasang 9, sumulat ng 1 ang magbago sa estadong 6". Sa orihinal na artikulo("On computable numbers, with an application to the Entscheidungsproblem"), ang pinag-gugunihan ni Turing ay hindi isang mekanismo ngunit isang persona na kanyang tinatawag na "kompyuter" na nagsasagawa ng mga determenistikong mekanikal na patakarang ito sa paraang gaya gaya o sa paglalarawan ni Turing "sa paraang walang paiba iba".

Sa mas tiyak na kahulugan, ang makinang Turing ay binubuo ng:

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 nangangahulugang 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.
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.
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_ia_j→q_i1a_j1d_k ngunit minsan ay 4-tuple) na kung ibinigay ang estadong(qi) na kasalukuyang estado ng makina at ang simbolong (a_j) kasalakuyang binabasa sa tape ay nagsasabi sa makina na isagawa ang sumusunod na sekwensiya(para sa mga modelong 5-tuple):
- Burahin o magsulat ng simbolo(imbis na a_j, isulat ang a_j1) at pagkatapos ay
- Ilipat ang ulo(na nilalarawan ng d_k at maaaring magkaroon ng mga halagang: 'L' para isang hakbang pakaliwa o R para sa hakbang na pakanan o N para manatili sa parehong lugar at pagkatapos ay
- Kunin ang pareho o bagong estado gaya ng inatas(pumunta sa estadong q_i1).
Sa mga modelong 4-tuple, mga instruksiyong "burahin o sumulat ng simbolo(a_j1)" at "ilipat ang ulo sa kaliwa o kanan (d_k)" ay tinutukoy bilang mga hiwalay na instruksiyon. Sa spesipikong paglalarawan, ang tabla ay nagsasabi sa makina na (ia) magbura o magsulat ng simbolo o (ib) ilipat ang ulo sa kaliwa o kanan at tapos (ii) ay kunin ang pareho o ang bagong estado gaya ng inatas ngunit hindi ang parehong mga aksiyon (ia) at (ib) sa parehong instruksiyon. Sa ilang mga modelo, kung walang entri sa tabla para sa kasalakuyang kombinasyon ng simbolo at estado, kung gayon ang makina ay hihinto. Ang ilang mga modelo ay nag-aatas na ang lahat ng mga entri ay dapat lagyan.
Ang isang rehistro(register) ng estado ay nag-iimbak ng estado ng makinang Turing na isa sa maraming may hangganan. Mayroong isang espesyal na simulang estado kung saan ang rehistro ng estado ay binibigyan ng simulang halaga. Ang mga estadong ito ayon kay Turing ay nagpapalit ng "estado ng isipan" ng isang taong nagsasagawa ng mga komputasyon sa ordinaryong kinalalagyan nito.

Dapat tandaan na ang bawat bahagi ng makina—ang mga koleksiyon ng estado at simbolo nito gayundin ang mga aksiyon nito—ang pagmamarka, pagbubura at mosyon ng tape ay may hangganan, diskreto at makikilala. Ang potensiyal na walang limitasyong halaga ng tape ang nabibigay dito ng walang hangganang halaga ng espasyo ng pag-iimbakan.

Mga halimbawa ng mga makinang Turing

Ang kauna-unahang makina ni Alan Turing
Copy routine(rutinang kopya)
3-estado abalang beaver

Pormal na depinisyon

Pormal na inilarawan nina Hopcroft and Ullman (1979, p. 148) ang(isang-tape) na makinang Turing bilang 7-tuple $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q_{0},F\rangle$ kung saan ang

$Q$ ang may hangganan hindi-walang laman na pangkat ng mga estado
$\Gamma$ ang may hangganan hindi-walang laman na pangkat ng mga alpabeto/simbolo ng tape
$b\in \Gamma$ ang simbolong blanko(ang tanging simbolong pinapayagan na makikita sa tape ng walang hanggan sa bawat hakban ng pagkukwenta)
$\Sigma \subseteq \Gamma \setminus \{b\}$ ang pangkat ng mga simbolong input
$q_{0}\in Q$ ang inisyal na estado
$F\subseteq Q$ ang pangkat ng pinal o tumatanggap na mga estado
$\delta :Q\setminus F\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}$ ay isang parsiyal na punsiyon na tinatawag na punsiyong transisyon kung saan ang L ay paglipat sa kaliwa, R ang paglipat sa kanan. Ang isang hindi karaniwang uri ay pumapayag sa "walang paglipat" na sabihing N bilang ikatlong elemento ng panghuling pangkat.)

Ang anumang nagsasagawa ng operasyon ayon sa mga spesipikasyong ito ay isang makinang Turing.

Ang 7-tuple para sa 3-estadong abalang beaver ay mukhang ganito:

Q = { A, B, C, HALT(HINTO) }

Γ = { 0, 1 }

b = 0 = "blanko"

Σ = { 1 }

δ = tingan ang tabla ng estado sa ibaba

q₀ = A = inisyal na estado

F = ang isang elementong pangkat ng mga pinal na estado{HALT(HINTO)}

Sa simula, ang lahat ng mga selula ng tape ay minamarkahan ng 0.

Tabla ng estado para sa 3 estado, 2 simbolong busy beaver
simbolo sa Tape	Kasalukuyang estado A			Kasalukuyang estado B			Kasalukuyang estado C
simbolo sa Tape	Isulat ang simbolo	Ilipat ang tape	Kasunod na estado	Isulat ang simbolo	Ilipat ang tape	Kasunod na estado	Isulat ang simbolo	Ilipat ang tape	Kasunod na estado
0	1	R	B	1	L	A	1	L	B
1	1	L	C	1	R	B	1	R	HALT(HINTO)

Mga sanggunian