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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} konačna abeceda i Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma^*} Kleeneova zatvorenost nad Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} . Tada je Semi-Thue sustav n-torka Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle T:=(\Sigma ,R)} sa
- Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R \subseteq \Sigma^* \times \Sigma^*.}
Elementi od R se zovu produkcije ili pravila (prepisivanja), i obično se pišu kao pravila Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u \rightarrow v} . Valja uočiti da R može biti beskonačan. Ako je semi-Thue sustav simetričan (tj. Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T:=(\Sigma, R)} i dvije riječi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u, v \in \Sigma^*} , može li Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} biti transformiran u Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} primjenom pravila iz Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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 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.
Pogreška pri izradbi sličice:
Nedovršeni članak Semi-Thue sustav koji govori o računarstvu treba dopuniti. Dopunite ga prema pravilima uređivanja Hrvatske internetske enciklopedije.
