Ma zimanek naskirî dikare binekomek zimanê biryardar pêk bîne?
Ji bo çareserkirina pirsa gelo zimanekî naskirî yê Turing dikare binekomek zimanek biryardar pêk bîne, pêdivî ye ku meriv têgehên bingehîn ên teoriya tevliheviya hesabkirinê bihesibîne, nemaze li ser dabeşkirina zimanan li ser bingeha biryardarbûn û naskirina wan hûr bibe.
Di teoriya tevliheviya hesabkirinê de, ziman komek rêzikên li ser hin alfabeyê ne, û ew dikarin li gorî celebê pêvajoyên hesabkirinê yên ku dikarin wan nas bikin an biryar bidin werin dabeş kirin. Zimanek tê gotin Turing naskirin (an bi paşvekişandinê têne hejmartin) heke makîneyek Turing hebe ku dê rêzika ku aîdî ziman e rawestîne û qebûl bike. Lêbelê, heke rêzik ne aîdê zimên be, makîneya Turing dikare wê red bike an jî bê rawestan bimeşîne. Ji aliyê din ve zimanek e biryardar (an vegerandin) heke makîneyek Turing hebe ku dê her gav bisekine û rast biryarê bide ka rêzika hatî dayîn aîdî ziman e yan na.
Pênase û Taybetmendî
1. Zimanên naskirî yên Turing:
- Zimanek (L) Turing tê nasîn heke makîneyek Turing (M) hebe ku ji bo her rêzek (w):
– Eger (w di L de), wê demê (M) di dawiyê de disekine û (w) dipejirîne.
– Eger (w notin L), wê demê (M) yan (w) red dike yan jî bê rawestan heta hetayê dimeşîne.
2. Zimanên biryardar:
- Zimanek (L) biryardar e ger makîneyek Turing (M) hebe ku ji bo her rêzek (w):
– Eger (w di L de), wê demê (M) di dawiyê de disekine û (w) dipejirîne.
– Ger (w notin L), wê demê (M) di dawiyê de disekine û (w) red dike.
Ji van pênaseyan diyar dibe ku her zimanekî biryardar di heman demê de Turing jî tê naskirin ji ber ku makîneya Turing a ku zimanek biryar dide dê her dem bisekine û bersivek bide, bi vî rengî ziman jî nas bike. Lêbelê, danûstendin ne hewce ye ku rast e ji ber ku zimanek naskirî ya Turing garantî nake ku makîneya Turing dê ji bo têlên ne di ziman de raweste.
Têkiliya Subset
Ji bo ku hûn diyar bikin ka zimanek naskirî ya Turing dikare binekomek zimanek biryardar ava bike, jêrîn bifikirin:
- Pênase Binkom: Zimanek ( A ) binkomeka zimanê ( B ) ye, wekî ( A binseteq B ) tê binavkirin, eger her rêzika ( A )yê jî di ( B ) de be. Bi fermî, (hemû w di A de, w di B de).
Ji ber ku her zimanek biryardar di heman demê de Turingî jî naskirî ye, mimkun e ku zimanek naskirî yê Turing bibe beşek ji zimanek biryardar. Ev ji ber vê yekê ye ku zimanê biryardar (B) dikare wekî zimanek Turing-ya naskirî bi taybetmendiya zêde ya ku ew li ser hemî têketinê radiweste were dîtin. Ji ber vê yekê, heke (A) Turing were naskirin û (B) biryardar be, û heke her rêzika di (A) de jî di (B) de be, wê demê (A) bi rastî dikare binekomek (B) be.
Nimûne û Nîşan
Ji bo ronîkirina vê têgînê, li mînakên jêrîn binêrin:
1. 1:
- Bila ( L_1 ) bibe zimanê hemî rêzikên ku bernameyên C-ya derbasdar şîfre dikin û dema ku têketinek neyê dayîn disekinin. Ev ziman wekî biryardar tê zanîn ji ber ku em dikarin makîneyek Turing ava bikin ku her bernameyek C-yê simule dike û diyar dike ka ew disekine.
– Bila ( L_2 ) bibe zimanê hemû rêzikên ku bernameyên C yên derbasdar şîfre dikin. Ev ziman Turing tê naskirin ji ber ku em dikarin makîneyek Turing ava bikin ku kontrol dike ka rêzek bernameyek C derbasdar e.
- Eşkere ye, ( L_2 subseteq L_1 ) ji ber ku her bernameyek C-ya derbasdar (çi raweste an nebe) di zimanê sekinandina bernameyên C de rêzek derbasdar e.
2. 2:
– Bila ( L_3 ) bibe zimanê ku ji hemû rêzikên li ser alfabeya ( {0, 1} ) pêk tê ku hejmarên binar li 3yê dabeşkirî temsîl dikin. ji sifir.
– Bila ( L_4 ) bibe zimanê ku ji hemû rêzikên binaryê ku jimareyên yekem temsîl dikin pêk tê. Ev ziman Turing tê naskirin ji ber ku em dikarin makîneyek Turing ava bikin ku bi ceribandina dabeşbûnê ve primality kontrol dike.
– Di vê rewşê de, ( L_4 ) ne binekomeka ( L_3 ) ye, lê eger em zimanê ( L_5 ) rêzikên binaryî yên ku hejmarên li 6-ê dabeşkirî (ku hem li 3-yê hem jî hettayê dabeşkirî ye) temsîl dikin, bihesibînin, wê demê (L_5 binseteq L_3 ).
Têkiliya biryardarbûn û naskirinê
Têkiliya di navbera zimanên biryardar û yên naskirî yên Turing de çend aliyên girîng eşkere dike:
- Taybetmendiyên Girtinê: Zimanên biryardar di bin yekbûn, hevgirtin û temamkirinê de têne girtin. Ev tê wê wateyê ku heke (L_1) û (L_2) biryardar bin, wusa ne (L_1 kasa L_2), (L_1 cap L_2), û (serxêz{L_1}) (tevgera (L_1)).
- Zimanên naskirî yên Turing: Ev di bin yekîtî û hevberdanê de girtî ne lê ne pêwîst e di bin temamkirinê de. Ev ji ber ku temamkerê zimanekî Turing naskirî dibe ku Turing neyê naskirin.
Encamên Praktîkî yên Di Ewlekariya Sîberê de
Têgihîştina têkiliyên di navbera zimanên naskirî û biryardar ên Turing de di ewlehiya sîber de, bi taybetî di çarçoveya verastkirina bernameyê û tespîtkirina malware de, bandorên pratîkî hene:
- Verification Program: Piştrastkirina ku bernameyek ji bo hemî têketinê rast tevdigere ji bo çînên taybetî yên bernameyan pirsgirêkek biryardar e. Mînakî, verastkirina ku algorîtmayek birêkûpêk bi rêkûpêk her navnîşek têketinê birêkûpêk dike dikare wekî pirsgirêkek biryardar were destnîşankirin.
- Tespîtkirina Malware: Tesbîtkirina ka bernameyek diyarkirî xirab e, dikare wekî pirsgirêkek naskirî ya Turing were çarçove kirin. Mînakî, hin heuristics an qalibên dikarin werin bikar anîn da ku malware-ya naskirî nas bikin, lê destnîşankirina ka bernameyek kêfî xirab e (pirsgirêka tespîtkirina malware) di rewşa gelemperî de neçar e.
Xelasî
Di eslê xwe de, zimanekî naskirî yê Turing bi rastî dikare binekomek zimanek biryardar pêk bîne. Ev têkilî strukturên hiyerarşîk ên çînên zimanî di teoriya tevliheviya hesabkerî de destnîşan dike, ku li wir zimanên biryardar binkomek zortir a zimanên naskirî yên Turing temsîl dikin. Ev têgihîştin ji bo serîlêdanên cihêreng ên di zanistiya komputer û ewlehiya sîber de girîng e, ku jêhatîbûna naskirin û biryardana zimanan di dabînkirina rastbûn û ewlehiya pergalên hesabker de rolek bingehîn dilîze.
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ê?
- 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?
- Pêvajoya veguhertina makîneyek Turing li komek çîpên ji bo PCP-ê vebêjin, û ka van pêlikan çawa dîroka hesabkirinê temsîl dikin.
Pir pirs û bersivan di Decidability de bibînin