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 $\Sigma$ konačna abeceda i $\Sigma ^{*}$ Kleeneova zatvorenost nad $\Sigma$. Tada je Semi-Thue sustav n-torka $T:=(\Sigma ,R)$ sa

$R\subseteq \Sigma ^{*}\times \Sigma ^{*}.$

Elementi od R se zovu produkcije ili pravila (prepisivanja), i obično se pišu kao pravila $u\rightarrow v$. Valja uočiti da R može biti beskonačan. Ako je semi-Thue sustav simetričan (tj. $R^{-1}=R$), 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 $T:=(\Sigma ,R)$ i dvije riječi $u,v\in \Sigma ^{*}$, može li $u$ biti transformiran u $v$ primjenom pravila iz $R$? 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 s 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

• Gramatika neograničenih produkcija

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 Wikipedije.