Ma gengaz e ku meriv diyar bike ka du rêzimanên bê kontekst heman zimanî qebûl dikin? Ma ev pirsgirêk çareser dibe?
Tesbîtkirina ka du rêzimanên bê kontekst heman zimanî qebûl dikin bi rastî gengaz e. Lêbelê, pirsgirêka biryardayina ka du rêzimanên bê kontekst heman zimanî qebûl dikin, ku wekî pirsgirêka "Wekheviya Rêzimanên Bê-Contekst" jî tê zanîn, neçar e. Bi gotinek din, algorîtmayek tune ku her gav bikaribe diyar bike ka du rêzimanên bê kontekst heman zimanî qebûl dikin an na.
Ji bo ku fêm bikin ka çima ev pirsgirêk neçar e, em hewce ne ku teoriya tevliheviya hesabkerî û têgeha biryardarbûnê bifikirin. Decidability qabiliyeta algorîtmayek ku her gav biqedîne û bersivek rast ji bo têketinek diyar çêbike vedibêje. Di mijara pirsgirêka "Wekheviya Rêzimanên Bê-Contekst" de, heke algorîtmayek biryarker hebûya, ew ê her gav raweste û rast diyar bike ka du rêzimanên bê kontekst heman zimanî qebûl dikin an na.
Delîla bêçareseriyê ji bo vê pirsgirêkê dikare bi kêmkirina wê li "Pirsgirêka Rawestandinê", ku di zanistiya komputerê de pirsgirêkek nebiryarkirî ya klasîk e, were saz kirin. Kêmkirin nîşan dide ku ger me ji bo pirsgirêka "Wekheviya Rêzimanên Bê-Context" algorîtmayek biryardar hebûya, me dikaribû wê ji bo çareserkirina "Pirsgirêka Rawestandinê", ya ku tê zanîn neçar e, bikar bînin. Ji ber ku "Pirsgirêka Rawestandinê" neçar e, ji ber vê yekê pirsgirêka "Wekheviya Rêzimanên Bê-Context" jî nayê çareser kirin.
Ji bo ku têgihîştinek bêtir intuitive peyda bikin, em mînakek bifikirin. Bifikirin ku me du rêzimanên bê kontekst G1 û G2 hene. G1 zimanê hemû palindroman li ser alfabeya {a, b} çêdike, lê G2 zimanê hemû rêzikên forma a^nb^n (ku n hejmareke erênî ye) çêdike. Bi intuîtîv, em dikarin bibînin ku ev her du rêziman heman zimanî naafirînin. Lêbelê, îsbatkirina vê yekê bi fermî karekî dijwar e, û algorîtmayek gelemperî tune ku bikaribe wê ji bo her cotek rêzimanên bê-contekst bike.
Neçareseriya pirsgirêka "Wekheviya Rêzimanên Bê-Context" di warên cihêreng ên zanistiya komputerê de, di nav de teoriya zimanê bernamekirinê, sêwirana berhevker, û pêvajokirina zimanê xwezayî, bandorên girîng hene. Ew sînorên hesabkirinê û hebûna pirsgirêkên ku bi algorîtmîkî nayên çareser kirin ronî dike.
Tesbîtkirina ka du rêzimanên bê kontekst heman zimanî qebûl dikin mimkun e, lê biryardayîna gelo ew dikin pirsgirêkek neçar e. Ev encam bi kêmkirina "Pirsgirêka Rawestandinê" ya nebiryar tê damezrandin. Bêçarebûna vê pirsgirêkê di warên cihêreng ên zanistiya komputerê de bandorên girîng hene.
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