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

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

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