Semi-Thue sustav

Izvor: Wikipedija
Skoči na: orijentacija, traži

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[uredi VE | uredi]

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[uredi VE | uredi]

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[uredi VE | uredi]

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 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[uredi VE | uredi]

Izvori[uredi VE | uredi]

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


Computer-aj aj ashton 01.svg Nedovršeni članak Semi-Thue sustav koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima Wikipedije.