Gava ku em di makîneyek ne-determînîst de du an bêtir rêyên meqbûl hebin, em kîjan hilbijêrin û em dikarin kîjan pîvanan bikar bînin?
Di warê teoriya tevliheviya hesabkerî de, bi taybetî di lêkolîna makîneyên rewşa dawî de, têgeha ne-determînîzmê rolek girîng dilîze.
Makîneyên dewleta dawîn ên ne-determînîst (NFSM) modelên teorîkî ne ku rê didin ku di her rewşek diyar de rêyên pir pejirandî werin girtin. Lê belê, dema ku bi rewşeke wiha re rû bi rû bimîne, pirsek derdikeve holê: divê kîjan rê were hilbijartin?
Ev pirs li ser têgîna "qebûlkirinê" ya di NFSM-an de û pîvanên ku dikarin ji bo girtina biryarekê werin bikar anîn vedigire.
Ji bo fêmkirina pêvajoya hilbijartinê, bila em pêşî xwezaya ne-determînîzmê ya di NFSM-an de bikolin. Berevajî makîneyên dewleta dawîn ên diyarker (DFSM), NFSM ji bo her sembola têketina gengaz a li her dewletê xwedan veguheztinek bêhempa ne. Di şûna wê de, ew ji bo heman sembola têketinê destûrê didin hebûna gelek veguherînan. Ev taybetmendî rê li ber îhtîmala hebûna gelek rêyên ku ji yek dewletek bişopîne, dibe sedema encamên cûda.
Dema ku bi rewşek wusa re rûbirû dibin, NFSM mekanîzmayek bi navê "şaxkirin" bikar tînin da ku hemî rêyên gengaz bi hevdemî vekolin. Ev tê vê wateyê ku makîne gelek kopiyên xwe diafirîne, her yek rêyek cûda dişopîne. Wekî encamek, NFSM dikare wekî vekolîna avahiyek mîna darê were dîtin, ku her şax rêyek hesabkirinê ya cihêreng temsîl dike. Ev teknîka şaxkirinê di analîzkirina NFSM û tevliheviya wan a hesabkirinê de bingehîn e.
Naha, bila em pîvanên ku dikarin werin xebitandin ji bo hilbijartina rêyek taybetî di nav pirên pejirandî de binirxînin. Nêzîkatiyek hevpar ev e ku meriv têgeha "pejirandinê" di NFSM-an de bihesibîne. Pejirandin şertê ku destnîşan dike ka têketinek diyar ji hêla makîneyê ve derbasdar tê hesibandin an na. Di NFSM-an de, pejirandin dikare bi du awayên sereke were destnîşankirin: "qebûlkirina ji hêla dewleta dawîn ve" û "qebûlkirina ji hêla stûna vala."
Qebûlkirina ji hêla dewleta paşîn ve gava ku, bi vexwarina tevahî rêzika têketinê re, NFSM di rewşek ku wekî rewşek paşîn hatî destnîşan kirin bi dawî dibe. Ev pîvan tê vê wateyê ku makîneya têketinê qebûl dike heke bi kêmî ve rêyek hesabkirinê hebe ku berbi rewşek dawîn ve diçe. Berevajî vê, heke rêyek berbi rewşek dawîn ve neçe, têketin tê red kirin.
Ji hêla din ve, pejirandina ji hêla stûna vala ve têkildar e dema ku NFSM stokek wekî hêmanek zêde vedihewîne. Di vê senaryoyê de, pejirandin dema ku rêzika têketinê bi tevahî were pêvajo kirin, û stûn vala dibe. Mîna pejirandina ji hêla dewleta dawîn ve, heke bi kêmî ve rêyek hesabkirinê hebe ku di stûnek vala de encam dide, têketin tê pejirandin; wekî din, ew tê red kirin.
Ji ber van pîvanan, hilbijartina rêgezek taybetî di nav gelek yên pejirandî de di makîneyek ne-determînîst de dikare bi pêşanîkirina şertên pejirandinê were destnîşankirin. Mînakî, heke pejirandina ji hêla dewleta dawîn ve pîvana bingehîn be, makîne dê riya ku berbi rewşek paşîn ve diçe hilbijêrin, bêyî ku rêyên din ên potansiyel bigire. Berevajî vê, heke pejirandina ji hêla stûna vala ve pîvana bingehîn be, makîne dê rêça ku di stûnek vala de bi encam dibe pêşîn bike.
Girîng e ku bala xwe bidinê ku bijartina rê di NFSM-an de bandorê li hêza hesabker a makîneyê nake. Bêyî ku riya hilbijartî hebe, NFSM dîsa jî dikare heman koma zimanan wekî her NFSM-ya din ji bo têketinek diyar nas bike. Pêvajoya hilbijartinê tenê li ser bingeha pîvanên diyarkirî pejirandin an redkirina têketinê diyar dike.
Dema ku di makîneyek ne-determînîst de bi gelek riyên pejirandî re rû bi rû bimîne, bijartina rê dikare bi pêşanî şert û mercên pejirandinê ve were destnîşankirin, wek pejirandina ji hêla dewleta dawîn an pejirandina ji hêla stûnek vala ve. Pêvajoya hilbijartinê bandorê li hêza hesabker a makîneyê nake lê bandorê li pejirandin an redkirina têketinê dike.
Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:
- Ji bo têgihîştina formalîzma teoriya tevliheviya hesabkirinê, çend pênaseyên bingehîn ên matematîkî, nîşan û danasîn çi ne?
- Çima teoriya tevliheviya hesabkirinê ji bo têgihîştina bingehên krîptografî û ewlehiya sîber girîng e?
- Rola teorema vegerê di xwenîşandana nebiryarbûna ATM de çi ye?
- Dema ku PDA-ya ku dikare palindroman bixwîne bihesibîne, gelo hûn dikarin geşedana stikê bi hûrgulî hûrgulî bikin dema ku têketin, yekem, palindromek, û ya duyemîn jî, ne palindrom be?
- Bi berçavgirtina PDA-yên ne-determînîst, lihevkirina dewletan ji hêla pênasê ve gengaz e. Lêbelê, PDA-yên ne-determînîst tenê stekek heye ku nekare bi hevdemî di gelek dewletan de be. Ev çawa gengaz e?
- Mînaka PDA-yan çi ye ku ji bo analîzkirina seyrûsefera torê û nasîna qalibên ku binpêkirinên ewlehiyê yên potansiyel destnîşan dikin tê bikar anîn?
- Wateya wê çi ye ku zimanek ji yê din bi hêztir e?
- Ma zimanên hesas ên kontekstê ji hêla Makîneya Turing ve têne nas kirin?
- Çima ziman U = 0^n1^n (n>=0) ne rêkûpêk e?
- Meriv çawa FSM rêzikên binary bi hêjmarên '1' yên zewac nas dike pênase bike û nîşan bide ku dema ku rêzika têketinê 1011 hildiweşîne çi diqewime?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin