WikiSysop: Bot: Automatski unos stranica

2021-08-23T06:48:58Z

Bot: Automatski unos stranica

Nova stranica

U [[računarstvo|računarstvu]] i [[matematika|matematici]], '''Semi-Thue sustav''' je sustav [[prepisivanje stringa|prepisivanja stringa]]. Imenovan je po norveškom matematičaru [[Axel Thue|Axelu Thueu]], koji je bio pionir u bavljenju sustavima prepisivanja stringa u ranom 20. stoljeću.

== Definicija ==

Neka je <math>\Sigma</math> konačna [[abeceda (računarstvo)|abeceda]] i <math>\Sigma^*</math> [[Kleeneova zatvorenost]] nad <math>\Sigma</math>. Tada je '''Semi-Thue sustav''' [[n-torka]] <math>T:=(\Sigma, R)</math> sa
:<math>R \subseteq \Sigma^* \times \Sigma^*.</math>

Elementi od R se zovu ''produkcije'' ili ''pravila (prepisivanja)'', i obično se pišu kao pravila <math>u \rightarrow v</math>. Valja uočiti da R može biti beskonačan. Ako je semi-Thue sustav simetričan (tj. <math>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 [[logika|logiku]], te stvorio sustave kao što je [[propozicijska logika]], koji bi omogućili izražavanje općenitih matematičkih teorema u [[formalni jezik|formalnom jeziku]], te da tako budu dokazani i verificirani na automatski, mehanički način. Nada je ležala u tome da bi čin [[dokazivanje teorema|dokazivanja teorema]] tad mogao biti sveden na skup definiranih manipulacija nad skupom stringova. Naknadno se shvatilo da su semi-Thue sustavi izomorfni [[gramatika neograničenih produkcija|gramatikama neograničenih produkcija]], za koje se zna da su izomorfne [[Turingov stroj|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 [[Alonzo Church|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>T:=(\Sigma, R)</math> i dvije riječi <math>u, v \in \Sigma^*</math>, može li <math>u</math> biti transformiran u <math>v</math> primjenom pravila iz <math>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 [[problem zaustavljanja|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.

{{mrva-rač}}

[[Kategorija:Formalni jezici]]
[[Kategorija:Teorija računanja]]

Semi-Thue sustav - Povijest promjena

WikiSysop: Bot: Automatski unos stranica