Têkiliya di navbera zimanên Turing-naskirî û jimarvanan de çi ye?
Têkiliya di navbera zimanên Turing-naskirî û hejmarkeran de di şiyana wan a hevpar a ravekirin û manîpulekirina komek rêzan de ye. Di warê teoriya tevliheviya hesabkerî de, her du têgeh di têgihîştina sînorên hesabkirinê û dabeşkirina pirsgirêkan de li ser bingeha tevliheviya wan a hesabkirinê de rolên girîng dilîzin.
Zimanek ku Turing-naskirî ye, ku wekî zimanê paşveger-jimarbar jî tê zanîn, ji komek rêzikên ku ji hêla makîneya Turing ve têne pejirandin ve tê gotin. Makîneya Turing modelek teorîkî ya hesabkirinê ye ku dikare li gorî rêzek qaîdeyan li ser kasetek bêdawî bixwîne, binivîse û bimeşîne. Ger makîneyek Turing rêzek têketinê rawestîne û qebûl bike, wê hingê ew rêz beşek ji zimanê Turing-naskirî ye ku bi wê makîneyê ve girêdayî ye. Lêbelê, heke makîneya têketinê rawestîne û red bike, an heke ew bêdawî xebitîn bidomîne, rewşa rêzika têketinê nediyar dimîne.
Ji aliyê din ve, jimarvan amûrek hesabker e ku ji zimanekî yek bi yek rêzan çêdike, bi potansiyel di rêzek bêdawî de. Serjimarvanek dikare wekî celebek taybetî ya makîneya Turing were hesibandin ku rêzan bi rêzek taybetî derdixe, wek rêzika ferhengnasî. Ew dikare ji bo navnîşkirina hemî rêzikên zimanek were bikar anîn, her çend heke ziman bêdawî be jî dibe ku bi dawî nebe.
Têkiliya di navbera zimanên Turing-naskirî û hejmarkeran de bi têgîna pejirandin û afirandinê dikare were fêm kirin. Zimanek Turing-naskirî dikare ji hêla makîneya Turing ve were pejirandin, tê vê wateyê ku makîne dikare her rêzek zimanî nas bike û bisekine. Berevajî vê, jimarvanek dikare rêzikên zimanekî bi rêzkirina wan bi rêkûpêk, bi potansiyel di rêzek bêdawî de biafirîne.
Girîng e ku em bala xwe bidinê ku ne hemî zimanên ku Turing-naskirî ne xwediyê jimarvan in, û ne hemî jimarvan bi zimanên Turing-naskirî re têkildar in. Mînakî, zimanên Turing-naskirî hene ku nayên biryardan, tê vê wateyê ku makîneyek Turing tune ku bikaribe her rêzika têketinê rawestîne û qebûl bike an red bike. Di rewşên weha de, jimarvanek nikare hebe ji ber ku ew zimanek biryardar e.
Ji aliyê din ve, ziman hene ku ji hêla jimarvanek ve têne çêkirin lê ji hêla makîneya Turing ve nayên naskirin. Mînaka zimanekî wiha, komeka hemû delîlên derbasdar di sîstemeke fermî de ye. Digel ku jimarvanek dikare bi rêkûpêk delîlên derbasdar biafirîne, dibe ku makîneyek Turing tune be ku bikaribe hemî delîlên derbasdar ji ber nebiryarbûn an netemambûna pergala fermî nas bike.
Têkiliya di navbera zimanên Turing-naskirî û hejmarkeran de ev e ku her du têgeh bi komek rêzan re mijûl dibin. Zimanên Turing-naskirî ji hêla makîneyên Turing ve têne pejirandin, lê hejmarker ji zimanekî rêzan çêdikin. Lêbelê, ne hemî zimanên ku Turing-naskirî ne xwediyê jimarvan in, û ne hemî hejmarker bi zimanên ku Turing-naskirî re têkildar in. Hebûna jimarevanek ji bo zimanekî bi taybetmendî û sînorên ziman bi xwe ve girêdayî ye.
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