Buka umthombo wala Ukubhala kabusha

[[Imathemathiki|Kumathematika]], isayensi yekhompiyutha, kanye nokunengqondo, '''ukubhala kabusha''' kuhlanganisa izindlela eziningi (okungenzeka zinganqumeli ) zokushintsha amagama angezansi efomula namanye amagama.Izinto okugxilwe kuzo zalesi sihloko zihlanganisa '''amasistimu okubhala kabusha''' (owaziwa nangokuthi '''amasistimu okubhala kabusha''', '''bhala kabusha izinjini''', <ref>
[[Joseph Goguen]] "Proving and Rewriting" International Conference on Algebraic and Logic Programming, 1990 Nancy, France pp 1-24</ref> <ref name="SculthorpeFrisby2014">{{Cite journal|last1=Sculthorpe|first1=Neil|last2=Frisby|first2=Nicolas|last3=Gill|first3=Andy|title=The Kansas University rewrite engine|journal=[[Journal of Functional Programming]]|volume=24|issue=4|year=2014|pages=434–473|issn=0956-7968|doi=10.1017/S0956796814000185|url=http://irep.ntu.ac.uk/id/eprint/27901/1/PubSub5454_Sculthorpe.pdf}}</ref> noma '''amasistimu okunciphisa''' ).Ngokwesimo sawo esiyisisekelo, aqukethe iqoqo lezinto, kanye nobudlelwano bokuthi zingaguqulwa kanjani lezo zinto.

Ukubhala kabusha kungase kunganqumi .Umthetho owodwa wokubhala kabusha igama ungasetshenziswa ngezindlela eziningi ezahlukene kulelo gama, noma kungasebenza umthetho ongaphezu kowodwa.Amasistimu okubhala kabusha awanikezi i- algorithm yokushintsha ithemu elilodwa ukuya kwelinye, kodwa isethi yemithetho engase isetshenziswe.Nokho, uma kuhlanganiswe ne-algorithm efanelekile, amasistimu okubhala kabusha angabhekwa njengezinhlelo zekhompyutha , futhi izaga ezimbalwa ze- <ref>{{Cite journal|doi=10.1016/0743-1066(92)90047-7|title=The term rewriting approach to automated theorem proving|journal=The Journal of Logic Programming|volume=14|issue=1–2|pages=71–99|year=1992|last1=Hsiang|first1=Jieh|last2=Kirchner|first2=Hélène|last3=Lescanne|first3=Pierre|last4=Rusinowitch|first4=Michaël}}</ref> nezilimi zokuhlela ezimemezelayo zisekelwe ekubhalweni kabusha kwethemu. <ref>{{Cite journal|doi=10.1016/S0743-1066(98)10005-5|title=Theory and practice of constraint handling rules|journal=The Journal of Logic Programming|volume=37|issue=1–3|pages=95–138|year=1998|last1=Frühwirth|first1=Thom}}</ref> <ref>{{Cite journal|doi=10.1016/S0304-3975(01)00359-0|title=Maude: Specification and programming in rewriting logic|journal=Theoretical Computer Science|volume=285|issue=2|pages=187–243|year=2002|last1=Clavel|first1=M.|last2=Durán|first2=F.|last3=Eker|first3=S.|last4=Lincoln|first4=P.}}</ref>

== Isibonelo samacala ==

=== Okunengqondo ===
Ngo logic, inqubo yokuthola ifomu evamile conjunctive (CNF) yefomula ezingase zithathwe njengoba uhlelo ubhalwe kabusha.Imithetho yesibonelo sesistimu enjalo ingaba:

: <math>\neg\neg A \to A</math> ( ukuchithwa okuphindwe kabili )
: <math>\neg(A \land B) \to \neg A \lor \neg B</math> (Imithetho kaDe Morgan )
: <math>\neg(A \lor B) \to \neg A \land\neg B</math>
: <math> (A \land B) \lor C \to (A \lor C) \land (B \lor C)</math> ( ukusabalalisa )
: <math> A \lor (B \land C) \to (A \lor B) \land (A \lor C),</math> <ref group="note">This variant of the previous rule is needed since the commutative law ''A''∨''B'' = ''B''∨''A'' cannot be turned into a rewrite rule. A rule like ''A''∨''B'' → ''B''∨''A'' would cause the rewrite system to be nonterminating.</ref>

lapho inombolo ( <math>\to</math> ) kubonisa ukuthi isisho esihambisana nesandla sobunxele somthetho singabhalwa kabusha sibe sisohlangothini lwesandla sokudla, futhi izimpawu ngayinye isho umusho ongaphansi.Esimisweni esinjalo, umthetho ngamunye ukhethwa ukuze uhlangothi lwesobunxele lulingane nohlangothi lwesokudla, futhi ngenxa yalokho lapho uhlangothi lwesobunxele lufana ne-subexpression, ukubhala kabusha kwaleyo nkulumo engaphansi ukusuka kwesobunxele kuya kwesokudla igcina ukuvumelana okunengqondo kanye nenani layo yonke inkulumo. .

=== I-Arithmetic ===
Amasistimu okubhala kabusha ethemu angasetshenziswa ukubala ukusebenza kwezibalo [[Inombolo Yokubala|ezinombolweni zemvelo]] .Ukuze wenze lokhu, inombolo ngayinye enjalo kufanele ifakwe ikhodi njengetemu .Umbhalo wekhodi olula yilowo osetshenziswa ku- axiom ye -Peano, esekelwe ku-0 (zero) ongashintshi kanye nomsebenzi womlandeli u- ''S'' . isibonelo, izinombolo 0, 1, 2, kanye no-3 zimelelwe imigomo 0, S(0), S(S(0)), kanye S(S(S(0))), ngokulandelana.Uhlelo olulandelayo lokubhala kabusha lungasetshenziswa ukubala isamba nomkhiqizo wezinombolo zemvelo ezinikeziwe. 

: <math>\begin{align}
A + 0    &\to A        & \textrm{(1)}, \\
A + S(B)   &\to S (A + B)    & \textrm{(2)}, \\
A \cdot 0  &\to 0        & \textrm{(3)}, \\
A \cdot S(B) &\to A + (A \cdot B) & \textrm{(4)}.
\end{align}</math>

Isibonelo, ukubalwa kuka-2+2 ukuze kuphumele ku-4 kungaphindwa ngokuphinda kubhalwe igama ngale ndlela elandelayo:

: <math>S(S(0)) + S(S(0))</math> <math> 
\;\;\stackrel{(2)}{\to}\;\; </math> <math>S( \; S(S(0)) + S(0) \; ) </math> <math>
\;\;\stackrel{(2)}{\to}\;\; </math> <math>S(S( \; S(S(0)) + 0 \; )) </math> <math>
\;\;\stackrel{(1)}{\to}\;\; </math> <math>S(S( S(S(0)) )),</math>

lapho izinombolo zomthetho zinikezwa ngenhla komcibisholo ''obhala kabusha.''

Njengesinye isibonelo, ukubalwa kwe-2⋅2 kubukeka kanje:

: <math>S(S(0)) \cdot S(S(0))</math> <math> 
\;\;\stackrel{(4)}{\to}\;\; </math> <math>S(S(0)) + S(S(0)) \cdot S(0) </math> <math>
\;\;\stackrel{(4)}{\to}\;\; </math> <math>S(S(0)) + S(S(0)) + S(S(0)) \cdot 0</math> <math>
\;\;\stackrel{(3)}{\to}\;\; </math> <math>S(S(0)) + S(S(0)) + 0)</math> <math>
\;\;\stackrel{(1)}{\to}\;\; </math> <math>S(S(0)) + S(S(0))</math> <math>
\;\;\stackrel{\textrm{s.a.}}{\to}\;\; </math> <math>S(S( S(S(0)) )),</math>

lapho isinyathelo sokugcina sihlanganisa isibonelo sangaphambilini sokubala.

=== Isayensi yezilimi ===
Ezifundweni zolimi, imithetho yesakhiwo samagama, ebizwa nangokuthi '''imithetho yokubhala kabusha''', isetshenziswa kwezinye izinhlelo zohlelo lolimi olukhiqizayo,njengendlela yokukhiqiza imisho elungile ngokohlelo lolimi.Umthetho onjalo ngokuvamile uthatha uhlobo A → X, lapho u-A eyilebula yesigaba sokwenziwa , njengebinzana lebizo noma [[umusho]], futhi u-X uwukulandelana kwalawo malebula noma amamofimu, okuveza iqiniso lokuthi u-A angathathelwa indawo ngu-X ekukhiqizeni isakhiwo somusho.Isibonelo, umthetho othi S → NP VP usho ukuthi umusho ungaqukatha ibinzana eliyibizo elilandelwa umusho wesenzo ; eminye imithetho izocacisa ukuthi ibinzana lebizo nebinzana lesenzo lingaqukatha ini, njalo njalo.

== Amasistimu okubhala kabusha angabonakali ==
Kulezi zibonelo ezingenhla, kusobala ukuthi singacabanga ngokubhala kabusha amasistimu ngendlela engabonakali.Kudingeka sicacise isethi yezinto kanye nemithetho engasetshenziswa ukuze siziguqule.Isilungiselelo esivame kakhulu (esingavamile) salo mbono sibizwa ngokuthi ''isistimu yokunciphisa'' <ref name="Book and Otto, p. 10">Book and Otto, p. 10</ref> noma ''isistimu yokubhala kabusha engabonakali'' (isifinyezo se- ''ARS'' ). <ref>Bezem et al., p. 7,</ref>I-ARS imane iyisethi engu- ''A'' yezinto, kanye nokuhlobana okumbambambili → ku- ''A'' okubizwa ngokuthi ''ubuhlobo bokunciphisa'', ''bhala kabusha ubuhlobo'' <ref>Bezem et al., p. 7</ref> noma nje ''ukunciphisa'' . <ref name="Book and Otto, p. 10" />

Imibono eminingi kanye nokuphawula kungachazwa kulungiselelo elivamile le-ARS. <math>\stackrel{*}{\rightarrow}</math> ukuvalwa kwe- reflexive transitive kwe <math>\rightarrow</math> . <math>\leftrightarrow</math> ukuvalwa kwe-symmetric ye <math>\rightarrow</math> . <math>\stackrel{*}{\,\leftrightarrow\,}</math> ukuvalwa kwe- reflexive transitive symmetric of <math>\rightarrow</math> . Igama elithi inkinga le-ARS liyanquma, kunikezwe u- ''x'' kanye no- ''y'', ukuthi ngabe <math>x \stackrel{*}{\,\leftrightarrow\,} y</math> . Into engu- ''x'' ku- ''A'' ibizwa ngokuthi i- ''reducible'' uma kukhona omunye u- ''y'' ku- ''A'' onjalo <math>x \rightarrow y</math> ; kungenjalo ibizwa ngokuthi i- ''irreducible'' noma ifomu elivamile . Into ethi ''y'' ibizwa ngokuthi "uhlobo olujwayelekile luka- ''x'' " uma <math>x \stackrel{*}{\,\rightarrow\,} y</math>, futhi ''y'' akanakuncishiswa. Uma uhlobo olujwayelekile luka- ''x'' luhlukile, lokhu kuvame ukuchazwa ngokuthi <math>x{\downarrow}</math> . Uma yonke into inefomu okungenani elilodwa elivamile, i-ARS ibizwa ngokuthi ''normalizing'' . <math>x \downarrow y</math> noma u- ''x'' kanye no- ''y'' kuthiwa ''angahlanganiswa'' uma kukhona okuthi ''z'' nempahla leyo <math>x \stackrel{*}{\,\rightarrow\,} z \stackrel{*}{\,\leftarrow\,} y</math> . Kuthiwa i-ARS inempahla ye- Church–Rosser uma <math>x \stackrel{*}{\,\leftrightarrow\,} y</math> kusho <math>x \downarrow y</math> . I-ARS ihlangana uma kukho konke u- ''w'', ''x'', kanye no- ''y'' kokuthi ''A'', <math>x \stackrel{*}{\,\leftarrow\,} w \stackrel{*}{\,\rightarrow\,} y</math> kusho <math>x \downarrow y</math> . I-ARS ihlangana ''endaweni'' uma futhi kuphela uma kubo bonke u- ''w'', ''x'', kanye no- ''y'' kokuthi ''A'', <math>x \leftarrow w \rightarrow y</math> kusho <math>x\mathbin\downarrow y</math> . Kuvele ARS kuthiwa ''oqeda'' noma ''noetherian'' uma kukhona akukho ketanga elingapheli <math>x_0 \rightarrow x_1 \rightarrow x_2 \rightarrow \cdots</math> . I-confluent ne-ARS eqedayo ibizwa ngokuthi i- ''convergent'' noma i- ''canonical'' .

Theorems Ezibalulekile Ezingafundwa izinhlelo abstract ubhalwe kabusha kukhona ukuthi ARS kuyinto confluent IFF it has impahla Church-Rosser, lemma Newman sika okuyinto sithi ARS ukuqeda kuyinto confluent kuphela uma kuba endaweni confluent, nokuthi inkinga izwi i ARS kuyinto undecidable ngenjwayelo.