Mînakek pirsgirêkek bide ku dikare ji hêla otomatek sînorkirî ya xêz ve were biryardan.
Otomaya sînorkirî ya xêzkirî (LBA) modelek hesabker e ku li ser kasetek têketinê dixebite û ji bo pêvajokirina têketinê mîqdarek bêdawî ya bîranînê bikar tîne. Ew guhertoyek sînorkirî ya makîneyek Turing e, ku serê kasêtê tenê dikare di nav rêzek tixûb de bimeşe. Di warê ewlehiya sîber û teoriya tevliheviya hesabkirinê de, LBA têne bikar anîn da ku biryardariya pirsgirêkên cihêreng analîz bikin.
Mînakek pirsgirêkek ku dikare ji hêla otomatek sînorkirî ve were biryardan pirsgirêka endametiya ziman e. Ji ber zimanek fermî L û rêzek w, pirsgirêk ew e ku were destnîşankirin ka w girêdayî L ye yan na. Ev pirsgirêk dikare ji hêla LBA-yê ve bi simulasyona hesabkirina makîneya Turing a ne-determînîst (NTM) ya ku L-yê biryar dide were çareser kirin.
Ji bo ronîkirina vê, em zimanê L = {0^n1^n | n ≥ 0}, ku ji hemû rêzikên bi jimareke wekhev 0-an pêk tê û li pey jimareke wekhev a 1-an pêk tê. Em dixwazin biryar bidin ka ristek w ya diyarkirî ya L ye.
LBA dikare bi şopandina kasêta têketinê ji çepê ber bi rastê ve dest pê bike, hejmara 0-yên ku pê re rû bi rû bihejmêre. Ew dikare bîra xwe ya bêdawî bikar bîne da ku jimartinê bişopîne. Dûv re, gava ku ew bi yekem 1-ê re rûbirû dibe, ew dikare dest bi şopandina beşa mayî ya kasêta têketinê bike, kontrol bike ka bi rastî heman hejmara 1-an heye ku hejmara 0-yên ku di bîranînê de tomar kiriye. Ger hejmar bihevre be, LBA dikare têketinê qebûl bike; wekî din, wê red dike.
Bi karanîna otomatek sînorkirî ya xêzkirî, em dikarin diyar bikin ka rêzek w ya diyarkirî ji zimanê L-yê re ye di demek bêdawî de û bi karanîna bîranînek sînorkirî. Ev biryardariya pirsgirêka endametiya ziman ji bo L.
Ji bo hin zimanên fermî ji bo çareserkirina pirsgirêka endametiya zimanî otomatek sînorkirî ya xêz dikare were bikar anîn. Bi simulkirina hesabkirina makîneya Turing a ne-determînîst, LBA dikare diyar bike ka rêzek diyarî aîdî zimanekî ye. Ev mînak serîlêdana pratîkî ya LBA-yê di warê ewlehiya sîber û teoriya tevliheviya hesabkirinê de ronî dike.
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?
- 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?
- Pêvajoya veguhertina makîneyek Turing li komek çîpên ji bo PCP-ê vebêjin, û ka van pêlikan çawa dîroka hesabkirinê temsîl dikin.
Pir pirs û bersivan di Decidability de bibînin