Di çarçoveya zimanên birêkûpêk de pirsek biryardar tê çi wateyê?
Pirsek biryardar, di çarçoweya zimanên birêkûpêk de, pirsek ku dikare bi algorîtmayek bi encamek rast garantîkirî ve were bersivandin vedibêje. Bi gotinek din, ew pirsek e ku pêvajoyek hesabkirinê heye ku dikare bersivê di demek bêdawî de diyar bike.
Ji bo têgihîştina têgeha pirsek biryardar a di çarçoweya zimanên rêkûpêk de, girîng e ku pêşî li zimanên rêkûpêk têgihîştinek zelal hebe. Zimanên bi rêkûpêk di zanistiya kompîturê de têgehek bingehîn e û ji bo danasîna şêwaz an komek rêzikên ku ji hêla otomatên bêdawî an biwêjên birêkûpêk ve têne nas kirin têne bikar anîn.
Decidability taybetmendiyek e ku çîna zimanan diyar dike ku ji hêla makîneya Turing an jî modelek din a hevwateya hevber ve dikare bi bandor were nas kirin. Zimanek dikare were biryardan heke algorîtmayek hebe ku, ji her rêzika têketinê re were dayîn, dikare diyar bike ka ew rêz aîdî ziman e yan na.
Di çarçeweya zimanên rêkûpêk de, pirseke birêkûpêk dikare bi vî awayî were formulekirin: Ji ber zimanekî rêkûpêk L û rêzeka w, gelo wa endamê L ye? Ev pirs dikare bi avakirina otomateke dawî ya ku zimanê L nas dike û otomatê li ser rêza têketina w bi simulekirina bersivê bide. Ger otomatê w qebûl bike, wê demê bersiva pirsê "erê" ye; Wekî din, bersiv "na" ye.
Mînakî, zimanê birêkûpêk L = {0, 1}* bihesibînin ku koma hemî rêzikên binaryê temsîl dike. Ji rêzek w = 101010 tê dayîn, pirsa biryardar dê ev be: Ma wa endamê L ye? Ji bo bersiva vê pirsê, em dikarin otomatek dawîn ava bikin ku zimanê L nas dike, û dûv re otomatê li ser rêza têketina w simule bikin. Ger otomatê bigihîje rewşek pejirandinê piştî ku tevahiya rêzika têketinê hilîne, wê hingê bersiv "erê" ye; Wekî din, bersiv "na" ye. Di vê rewşê de, otomatê dê bigihîje rewşek pejirandinê, ji ber vê yekê bersiv "erê" ye.
Di çarçoweya zimanên birêkûpêk de biryarbûn taybetmendiyek xwestek e ji ber ku ew piştrast dike ku algorîtmayek heye ku dikare pirsgirêka endamtiyê ji bo her zimanek birêkûpêk çareser bike. Vê taybetmendiyê di warên cihêreng ên zanistiya komputerê de, di nav de ewlehiya sîber, ku zimanên birêkûpêk bi gelemperî têne bikar anîn ji bo danasîna nimûneyên pergalên vedîtina destavêtinê an jî diyarkirina polîtîkayên kontrolkirina gihîştinê bandorên girîng hene.
Pirseke biryardar di çarçoveya zimanên birêkûpêk de pirsek ku dikare bi algorîtmayek bi encamek rast garantîkirî ve were bersivandin vedibêje. Ew pirsek e ku pêvajoyek hesabkirinê heye ku dikare bersivê di demek bêdawî de diyar bike. Di çarçoweya zimanên birêkûpêk de bijartî taybetmendiyek xwestek e ji ber ku ew hebûna algorîtmayek ku dikare pirsgirêka endamtiyê ji bo her zimanek birêkûpêk çareser bike misoger dike.
Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:
- Ji kerema xwe di bersivê de mînaka ku rêzika binaryê bi 1 sembolan jî FSM nas dike vebêje." …Rêşa têketinê "1011", FSM nagihîje rewşa dawîn û piştî hilanîna sê sembolên pêşîn di S0 de asê dimîne."
- Nedetermînîzm çawa bandorê li fonksiyona veguherînê dike?
- Ma zimanên birêkûpêk bi Makîneyên Dewleta Dawî re hevwate ne?
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- Li gorî Teza Church-Turing pirsgirêka ku ji hêla algorîtmîkî ve tê hesibandin pirsgirêkek e ku ji hêla Makîneyek Turing ve tê hesibandin?
- Taybetmendiya girtina zimanên birêkûpêk ên di bin hevgirtinê de çi ye? Makîneyên dewleta dawîn çawa li hev tên ku yekbûna zimanan bi du makîneyan tê naskirin temsîl bikin?
- Ma her pirsgirêkek kêfî dikare wekî zimanek were vegotin?
- Ma pola tevliheviya P binkomek pola PSPACE ye?
- Ma her makîneya Turing a pir-tape makîneyek Turing-a yek-tape wekhev heye?
- Berhemên predîkatan çi ne?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin