Semi-Thue sustav
U računarstvu i matematici, Semi-Thue sustav je sustav prepisivanja stringa. Imenovan je po norveškom matematičaru Axelu Thueu, koji je bio pionir u bavljenju sustavima prepisivanja stringa u ranom 20. stoljeću.
Definicija
Neka je [math]\displaystyle{ \Sigma }[/math] konačna abeceda i [math]\displaystyle{ \Sigma^* }[/math] Kleeneova zatvorenost nad [math]\displaystyle{ \Sigma }[/math]. Tada je Semi-Thue sustav n-torka [math]\displaystyle{ T:=(\Sigma, R) }[/math] sa
- [math]\displaystyle{ R \subseteq \Sigma^* \times \Sigma^*. }[/math]
Elementi od R se zovu produkcije ili pravila (prepisivanja), i obično se pišu kao pravila [math]\displaystyle{ u \rightarrow v }[/math]. Valja uočiti da R može biti beskonačan. Ako je semi-Thue sustav simetričan (tj. [math]\displaystyle{ R^{-1}=R }[/math]), tada se također zove Thue sustav.
Povijest i važnost
Semi-Thue sustavi su razvijeni kao dio programa koji bi dodao dodatne konstrukte u logiku, te stvorio sustave kao što je propozicijska logika, koji bi omogućili izražavanje općenitih matematičkih teorema u formalnom jeziku, te da tako budu dokazani i verificirani na automatski, mehanički način. Nada je ležala u tome da bi čin dokazivanja teorema tad mogao biti sveden na skup definiranih manipulacija nad skupom stringova. Naknadno se shvatilo da su semi-Thue sustavi izomorfni gramatikama neograničenih produkcija, za koje se zna da su izomorfne Turingovim strojevima. Pa iako je ovaj istraživački program uspio u smislu da računala mogu biti korištena za verificiranje dokaza teorema, nije uspio na spektaluran način: računalo ne može razlikovati između zanimljivog teorema, i onog dozlaboga dosadnog.
Na prijedlog Alonza Churcha, Emil Post je u radu objavljenom 1947. prvi dokazao nerješivost "određenog problema Thuea", što Martin Davis iskazuje kao "...prvi dokaz nerješivosti za problem klasične matematike - u ovom slučaju problem riječi za polugrupe." (Undecidable, str. 292)
Davis tvrdi da je dokaz nezaivsno izveo A. A. Markov (C. R. (Doklady) Acad. Sci. U.S.S.R. (n.s.) 55(1947), str. 583-586.
Problem riječi za semi-Thue sustave
Problem riječi za semi-Thue sustave se može iskazati na sljedeći način: Za dani semi-Thue sustav [math]\displaystyle{ T:=(\Sigma, R) }[/math] i dvije riječi [math]\displaystyle{ u, v \in \Sigma^* }[/math], može li [math]\displaystyle{ u }[/math] biti transformiran u [math]\displaystyle{ v }[/math] primjenom pravila iz [math]\displaystyle{ R }[/math]? Ovaj je problem neodlučiv, tj. ne postoji općenit algoritam za rješavanje ovog problema. Ovo vrijedi čak i ako se ograniči ulaz konačnih sustava.
Martin Davis nudi laičkom čitatelju dvostrani dokaz u svom članku What is a Computation?" str. 258-259 sa komentarom na str. 257. Davis dokaz izvodi na ovaj način: "izmisli [problem riječi] čije bi rješenje vodilo ka rješenju problema zaustavljanja."
Vidjeti također
Izvori
- Martin Davis ed. (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, Raven Press, New York.
- Emil Post (1947), Recursive Unsolvability of a Problem of Thue, pretisak u The Undecidable str. 293 u The Journal of Symbolic Logic, vol. 12 (1947) str. 1-11.
Nedovršeni članak Semi-Thue sustav koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima uređivanja Hrvatske internetske enciklopedije.