Pagkakaiba sa mga pagbabagong ng "Makinang Turing"

m
walang buod ng pagbabago
m
m
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 [[teoriya ng kompleksidad]].
 
==InpormalImpormal 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 hanaypangkat 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".
 
[[Talaksan:Turing machine 2b.svg|thumb|right|300px|Dito, ang panloob na estadong (q<sub>1</sub>) ay pinapakita sa loob ng ulo at ang ilustrasyon ay naglalarawan sa tape bilang walang hanggan at pinuno sa simula ng "0" na simbolong nagsisilbing blanko. Ang kabuuang estado ng sistema(ang ''konpigurasyon'' nito) ay binubuo ng panloob na estado, ang mga nilalaman ng nalililimang mga parisukat na kinabibilangan ng blankong binasa ng ulo ("11B"), at ang posisyon ng ulo. (Drawing after Minsky (1967) p. 121).]]
 
Pormal na inilarawan nina Hopcroft and Ullman (1979, p.&nbsp;148) ang(isang-tape) na makinang Turing bilang 7-[[tuple]] <math>M= \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle</math> kung saan ang
* <math> Q </math> ang may hangganan hindi-walang laman na [[hanaypangkat (matematika)|pangkat]] ng mga ''estado''
* <math>\Gamma</math> ang may hangganan hindi-walang laman na hanaypangkat ng mga ''alpabeto/simbolo ng tape''
* <math>b \in \Gamma</math> ang ''simbolong blanko''(ang tanging simbolong pinapayagan na makikita sa tape ng walang hanggan sa bawat hakban ng pagkukwenta)
* <math>\Sigma\subseteq\Gamma\setminus\{b\}</math> ang hanaypangkat ng mga ''simbolong input''
* <math>q_0 \in Q</math> ang ''inisyal na estado''
* <math>F \subseteq Q</math> ang hanaypangkat ng ''pinal'' o ''tumatanggap na mga estado''
* <math>\delta: Q \setminus F \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}</math> 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 hanaypangkat.)
 
Ang anumang nagsasagawa ng operasyon ayon sa mga spesipikasyong ito ay isang makinang Turing.
:δ = tingan ang tabla ng estado sa ibaba
:q<sub>0</sub> = '''A''' = inisyal na estado
:F = ang isang elementong hanaypangkat ng mga pinal na estado{'''HALT(HINTO)'''}
 
Sa simula, ang lahat ng mga selula ng tape ay minamarkahan ng 0.
11,191

edit