Algorîtmaya ku pirsgirêka pejirandinê ji bo makîneyên Turing biryar dide, û ka ew çawa ji bo avakirina biryarderek ji bo pirsgirêka zimanê vala tê bikar anîn diyar bikin.
Pirsgirêka pejirandinê ji bo makîneyên Turing têgehek bingehîn e di teoriya tevliheviya hesabkirinê de, ku bi lêkolîna çavkaniyên ku ji hêla algorîtmayan ve hewce ne ji bo çareserkirina pirsgirêkên hesabkirinê re mijûl dibe. Di çarçoweya makîneyên Turing de, pirsgirêka pejirandinê diyar dike ka makîneyek Turing a diyar rêzek têketinê ya taybetî qebûl dike an na.
Ji bo ravekirina algorîtmaya ku pirsgirêka pejirandinê ji bo makîneyên Turing biryar dide, divê em xebata makîneyek Turing fam bikin. Makîneya Turing ji kasetek ku di nav şaneyan de hatî dabeş kirin, serê xwendin-nivîsandinê ku dikare li ser kasêtê bigere û yekîneyek kontrolê ya ku tevgera makîneyê diyar dike pêk tê. Yekîneya kontrolê bi gelemperî ji hêla makîneyek dewleta dawî ve tê temsîl kirin.
Algorîtmaya ku pirsgirêka pejirandinê ji bo makîneyên Turing biryar dide, tevlêbûna tevgera makîneya Turing a diyarkirî ya li ser rêzika têketinê pêk tîne. Ev simulasyon bi rengek gav-gav, li dû veguheztinên ku ji hêla yekîneya kontrolê ya makîneya Turing ve hatî destnîşan kirin, pêşve diçe.
Algorîtm bi destpêkirina kasêtê bi rêzika têketinê dest pê dike û serê xwendin-nivîsandinê li destpêka kasêtê bi cih dike. Dûv re, ew têkeve dorpêkek ku ew çend caran gavên jêrîn pêk tîne:
1. Nîşana di bin serê xwendin-nivîsandinê de bixwînin.
2. Rewşa niha ya makîneya Turing diyar bike.
3. Li fonksiyona veguherîna makîneya Turing bigerin da ku rewşa din û çalakiya ku li ser bingeha rewşa heyî û nîşana xwendinê were kirin bibînin.
4. Kaset û pozîsyona serê xwendin-nivîsandinê li ser bingeha çalakiya ku ji hêla fonksiyona veguherînê ve hatî destnîşan kirin nûve bikin.
5. Ger dewleta din dewletek qebûlker be, rêzika têketinê rawestîne û qebûl bike. Ger dewleta din dewletek redkirinê ye, rêzika têketinê rawestîne û red bike.
Ev algorîtma berdewam dike heya ku makîneya Turing di rewşek pejirandin an redkirinê de raweste. Ger makîneya Turing qet nesekine, algorîtma bi dawî nabe.
Ji bo avakirina biryarderek ji bo pirsgirêka zimanê vala bi karanîna algorîtmaya pirsgirêka pejirandinê, pêdivî ye ku em diyar bikin ka makîneyek Turing a diyar ti rêzek qebûl dike an na. Pirsgirêka zimanê vala dipirse gelo zimanê ku ji hêla makîneya Turing ve tê naskirin vala ye ango, ew ti rêzek qebûl nake.
Ji bo çareserkirina pirsgirêka zimanê vala, em dikarin algorîtmaya pirsgirêka pejirandinê wekî jêrîn bikar bînin:
1. Dema ku makîneyek Turing tê dayîn, makîneyek Turing a nû ava bike ku tevgera makîneya Turing a orîjînal li ser hemî têlên têketinê yên gengaz simule dike.
2. Algorîtmaya pirsgirêka pejirandinê li ser makîneya Turing a nû hatî çêkirin bimeşîne.
3. Ger algorîtmaya pirsgirêka pejirandinê raweste û her rêzika têketinê qebûl bike, wê hingê makîneya Turing a orîjînal bi kêmanî yek rêzek qebûl dike, û pirsgirêka zimanê vala derew e.
4. Ger algorîtmaya pirsgirêka pejirandinê hemî rêzikên têketinê rawestîne û red bike, wê hingê makîneya Turing a orîjînal tu rêzikan qebûl nake, û pirsgirêka zimanê vala rast e.
Bi karanîna algorîtmaya pirsgirêka pejirandinê, em dikarin ji bo pirsgirêka zimanê vala biryardarek ava bikin, ku diyar dike ka makîneya Turing a diyar ti rêzek qebûl dike yan na.
Algorîtmaya ku pirsgirêka pejirandinê ji bo makîneyên Turing biryar dide, tevlêbûna tevgera makîneya Turing li ser rêzika têketinê pêk tîne. Bi karanîna vê algorîtmayê, em dikarin ji bo pirsgirêka zimanê vala biryarderek ava bikin, ku diyar dike ka makîneya Turing a diyar ti rêzek qebûl dike yan na.
Pirs û bersivên din ên vê dawiyê di derbarê Biryardarî:
- Ma kasetek dikare bi mezinahiya têketinê ve were sînordar kirin (ku wekhev e ku serê makîneya turingê bi sînorkirî ye ku ji têketina kasêta TM-yê wêdetir bimeşe)?
- Wateya guhertoyên cihêreng ên Makîneyên Turing di kapasîteya hesabkirinê de tê çi wateyê?
- Ma zimanek naskirî dikare binekomek zimanê biryardar pêk bîne?
- Pirsgirêka rawestandina makîneyek Turing biryardar e?
- Ger du TM-yên me hene ku zimanek biryardar diyar dikin, gelo pirsa wekheviyê hîn jî nayê biryar?
- Pirsgirêka pejirandinê ji bo otomatên xêzkirî ji ya makîneyên Turing çawa cûda dibe?
- Mînakek pirsgirêkek bide ku dikare ji hêla otomatek sînorkirî ya xêz ve were biryardan.
- Di çarçoweya otomatên sînorkirî yên rêzê de têgeha biryardarbûnê rave bikin.
- Mezinahiya kasêtê di otomatên xêzkirî de çawa bandorê li hejmara veavakirinên cihê dike?
- Cûdahiya sereke di navbera otomatên sînorkirî yên rêzkirî û makîneyên Turing de çi ye?
Pir pirs û bersivan di Decidability de bibînin