Makinang Turing: Pagkakaiba sa mga binago
Content deleted Content added
mNo edit summary |
mNo edit summary |
||
Linya 8:
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]].
==
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
[[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).]]
Linya 36:
Pormal na inilarawan nina Hopcroft and Ullman (1979, p. 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 [[
* <math>\Gamma</math> ang may hangganan hindi-walang laman na
* <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
* <math>q_0 \in Q</math> ang ''inisyal na estado''
* <math>F \subseteq Q</math> ang
* <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
Ang anumang nagsasagawa ng operasyon ayon sa mga spesipikasyong ito ay isang makinang Turing.
Linya 53:
:δ = tingan ang tabla ng estado sa ibaba
:q<sub>0</sub> = '''A''' = inisyal na estado
:F = ang isang elementong
Sa simula, ang lahat ng mga selula ng tape ay minamarkahan ng 0.
| |||