Ma her pirsgirêkek kêfî dikare wekî zimanek were vegotin?

Di warê teoriya tevliheviya hesabkirinê de, têgîna îfadekirina pirsgirêkan wekî ziman bingehîn e. Ji bo ku em vê pirsê çareser bikin divê em bingehên teorîkî yên hesabkirin û zimanên fermî binirxînin.

"Ziman" di teoriya tevliheviya hesabkerî de komek rêzikên li ser alfabeyek bêdawî ye. Ew avahiyek fermî ye ku dikare ji hêla modelek hesabker ve were nas kirin, wekî makîneya Turing. Ev têgeh di teoriya zimanê fermî de ye, ku taybetmendiyên hevoksazî yên zimanên fermî û dabeşkirina wan lêkolîn dike.

Ji bo ku em fêm bikin ka her pirsgirêkek keyfî dikare wekî zimanek were vegotin, divê em pêşî zelal bikin ka mebesta "pirsgirêka kêfî" çi ye. Di warê hesabkirinê de, pirsgirêk bi gelemperî pirsgirêkek biryarê an pirsgirêkek fonksiyonê vedibêje. Pirsgirêkek biryarê pirsek erê/na li ser têketinê dipirse, dema ku pirsgirêkek fonksiyonê ji bo têketinek diyar hesabek hilberek taybetî hewce dike.

Ji bo pirsgirêkên biryarê, girêdana bi zimanan re rasterast e. Pirsgirêka biryarê bi rastî dikare wekî zimanek were îfade kirin. Pirsgirêka biryarê (P) bihesibînin ku dipirse ka ketina diyarkirî (x) girêdayî komek (S) ye yan na. Ev pirsgirêk dikare bi zimanê (L) ku ji hemû rêzikên (x) pêk tê, ku bersiva (P(x)) "erê" ye, were temsîl kirin. Ji ber vê yekê, pirsgirêka biryarê (P) bi zimanê (L) re ye.

Mînakî, werin em pirsgirêka biryarê ya diyarkirina ka rêzikek binar ya diyar hejmarek zewac nîşan dide an na. Zimanê ku bi vê pirsgirêkê re têkildar e, komek ji hemî rêzikên binaryê ye ku bi '0' diqede, ji ber ku jimareyek binar heta heke û tenê heke bit-ya wê ya herî girîng 0 be jî, pirsgirêk dikare wekî ziman (L = { x di {0,1}^* nîvnivîsa x de{ bi } 0} diqede).

Pirsgirêkên fonksiyonê, ji hêla din ve, pirtirkêmtir in. Pirsgirêkek fonksiyonê ji girtina biryarek binary hewce dike ku nirxek hesab bike. Ji bo îfadekirina pirsgirêkek fonksiyonê wekî ziman, yek nêzîkbûn ev e ku meriv grafiya fonksiyonê binirxîne. Grafika fonksiyona ( f ) komek cotên rêzkirî ye ( (x, f(x))). Ev kom dikare wekî zimanek li ser alfabeyê were dîtin ku hem ji bo têketin û hem jî ji bo derketinan sembolan vedihewîne.

Mînakî, pirsgirêka fonksiyonê ya hesabkirina çargoşeya yekhejmarek binirxînin. Grafika vê fonksiyonê koma cotan e ( { (x, x^2) mid x di mathbb{Z} } de). Ev set dikare wekî zimanek li ser alfabeyek minasib were kod kirin. Lêbelê, ev nûnertî ji nûneriya rasterast a pirsgirêkên biryarê tevlihevtir e.

Şiyana îfadekirina pirsgirêkan wekî zimanan têgehek hêzdar e ji ber ku ew dihêle ku teoriya zimanê fermî û teoriya otomatê were bikar anîn da ku pirsgirêkên hesabkirinê analîz bike. Çînên zimanên ku ji hêla modelên hesabker ên cihêreng ve têne nas kirin, wekî zimanên birêkûpêk, zimanên bê kontekst, û zimanên ku bi paş ve têne hejmartin, bi çînên cûda yên pirsgirêkên biryarê re têkildar in.

Mînakî, zimanên birêkûpêk ew in ku dikarin ji hêla otomatên dawî ve bêne nas kirin. Ew bi pirsgirêkên biryarê re têkildar in ku dikarin bi mîqdarek bêdawî ya bîranînê ve werin çareser kirin. Zimanên bê-contekst, ku ji hêla otomatên pushdown ve têne nas kirin, dikarin pirsgirêkên ku hewceyê avahiyek bîranînê ya mîna stûnê hewce dikin destnîşan bikin. Zimanên ku bi vegerê têne hejmartin, ku ji hêla makîneyên Turing ve têne nas kirin, bi pirsgirêkên ku dikarin ji hêla komputerek gelemperî ya bi bîranîna bêsînor ve bêne çareser kirin re têkildar in.

Ji bo ku pêwendiya di navbera pirsgirêk û zimanan de bêtir nîşan bide, pirsgirêka navdar a destnîşankirina ka rêzikek diyarî palindrom e an na. Palindrom xêzek e ku bi pêş û paş ve yeksan dixwîne. Pirsgirêka biryarê ya kontrolkirina ka rêzikek palindrom e, dikare wekî ziman were diyar kirin (L = {x di Sigma^* mid x = x^R}), ku (x^R) berevajiya (x) nîşan dide.

Wekî din, têgeha kêmkirina pirsgirêkan di teoriya tevliheviya hesabkirinê de xwe dispêre vegotina pirsgirêkan wekî ziman. Kêmkirina ji pirsgirêka (A) bo pirsgirêka (B) rêyek e ku mînakên (A)-ê vediguherînin mînakên (B)-ê ku çareseriya (B) destûrê dide me ku em (A) çareser bikin. Ev veguhertin bi gelemperî wekî fonksiyonek ku rêzikên bi zimanê (A) bi rêzikên di zimanê (B) de vedihewîne, tê diyar kirin.

Mînakî, pirsgirêka destnîşankirina ka grafiyek dupartî ye, dikare bi pirsgirêka destnîşankirina ka grafîkek xwedan 2-rengdêrek rast e kêm bibe. Ev kêmkirin dikare wekî fonksiyonek ku mînakên pirsgirêka dupartîbûnê vediguhezîne mînakên pirsgirêka 2-rengdêriyê. Zimanê ku bi pirsgirêka dupartîbûnê re têkildar e, komek ji hemî şîfreyên grafîkan e ku grafikên dupartî temsîl dikin, û zimanê ku bi pirsgirêka 2-rengî re têkildar e koma hemî şîfreyên grafîkî ye ku xwediyê 2-rengdêrek rast e.

Wekî din, teoriya NP-temambûnê bi giranî xwe dispêre vegotina pirsgirêkan wekî ziman. Pirsgirêkek NP-temam e heke ew di NP-ê de be û her pirsgirêk di NP-ê de dikare di dema pirnomî de jê were kêm kirin. Çîna NP ji pirsgirêkên biryarê pêk tê ku ji bo wan bersivek "erê" dikare ji hêla algorîtmayek polînomî-dema nedetermînîst ve were verast kirin. Bilêvkirina van pirsgirêkan wekî ziman dihêle ku rêbazên fermî bikar bînin da ku NP-temamiya îsbat bikin.

Mînakî, pirsgirêka SAT, ku dipirse ka formula boolean a diyarkirî têr e, NP-temam e. Zimanê ku bi SAT-ê re têkildar e, komek hemî şîfreyên formulên boolean ên têrker e. Îspatkirina ku pirsgirêkek din, wekî pirsgirêka Clique, NP-temam e, tê de destnîşan dike ku SAT dikare li Clique were kêm kirin. Ev kêmkirin wekî fonksiyonek ku formulên boolean vediguherîne şîfreyên grafîkê tê diyar kirin.

Digel ku pirsgirêkên biryarê dikarin rasterast wekî zimanan bêne diyar kirin, pirsgirêkên fonksiyonê nûneriyek tevlihevtir hewce dike, ku pir caran grafiya fonksiyonê vedigire. Şiyana îfadekirina pirsgirêkan wekî zimanan kevirê bingehîn ê teoriya tevliheviya hesabkirinê ye, ku karanîna teoriya zimanî ya fermî ji bo analîzkirin û dabeşkirina pirsgirêkan dihêle. Ev nêzîkatî gelek têgehên bingehîn, wek kêmkirin, NP-temamî, û dabeşkirina zimanan ku ji hêla modelên cûda yên hesabkirinê ve têne nas kirin, vedihewîne.

Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:

• 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?
• 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?

Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin

Pirs û bersivên bêtir:

• Erd: Pîroz
• bernameya: EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê (biçin bernameya sertîfîkayê)
• Ders: Pêşkêş (biçin dersa têkildar)
• Mijar: Pêşgotina teorîk (biçin ser mijara têkildar)