Pirsgirêka zimanê vala di çarçoveya ewlehiya sîber de çi ye, û çima ew pirsek bingehîn di qadê de tê hesibandin?
Pirsgirêka zimanê vala di çarçeweya ewlehiya sîber de vê pirsê vedibêje ka gelo makîneyek Turing (TM) ti rêzikan qebûl dike, ango zimanê ku ji hêla TM ve hatî nas kirin vala ye. Ev pirsgirêk di warê ewlehiya sîber de girîngiyek girîng digire ji ber ku ew li ser aliyên bingehîn ên teoriya tevliheviya hesabkerî, bi taybetî têgeha biryardarbûnê disekine.
Di teoriya tevliheviya hesabkerî de, biryardarbûn bi destnîşankirina ka pirsgirêkek diyarkirî dikare bi algorîtmayek were çareser kirin re têkildar e. Pirsgirêka zimanê vala di bin vê kategoriyê de ye, ji ber ku ew digere ku diyar bike ka TM ti rêzek qebûl dike, ku dikare wekî pirsgirêkek biryarê were dîtin.
Ji bo fêmkirina girîngiya pirsgirêka zimanê vala, divê em bingehên makîneyên Turing binirxînin. Makîneya Turing modelek teorîkî ya hesabkirinê ye ku ji kasetek ku di nav şaneyan de hatî dabeş kirin, serê xwendin-nivîsandinê û yekîneyek kontrolê pêk tê. Yekîneya kontrolê komek rêbazan dişopîne, ku jê re fonksiyona veguherînê tê gotin, ku diyar dike ka makîneyê çawa li ser kasêtê dixebite.
TM rêzek dipejirîne heke, gava ku ew rêz wekî têketinê were dayîn, ew di rewşek pejirandinê de raweste. Berevajî vê, heke TM di rewşek nepejirandinê de nesekine an jî raweste, string nayê pejirandin. Pirsgirêka zimanê vala dipirse gelo TM heye ku qet rêzan qebûl nake, ango zimanê wî vala ye.
Ji bo çareserkirina vê pirsgirêkê, em dikarin delîlek bi nakokiyê bikar bînin. Bifikirin ku TM, M heye, ku ti rêzan qebûl nake. Em dikarin TM-ya din, M' ava bikin, ku hemî rêzan qebûl dike. M' bi vî rengî dixebite: ji ber ku her rêzika têketinê tê dayîn, ew M li ser wê têketinê simule dike. Ger M raweste û red bike, M' têketinê qebûl dike; wekî din, M' têketinê red dike. Ji ber vê yekê, M' hemî rêzan qebûl dike, berbi nakokiyê ve dibe. Ev nakokî tê vê wateyê ku TMyek ku têlan qebûl nake tune be, û ji ber vê yekê pirsgirêka zimanê vala nayê çareser kirin.
Bêçarebûna pirsgirêka zimanê vala bandorên kûr li ser ewlehiya sîber heye. Ew sînorên hesabkirinê û hebûna pirsgirêkên ku bi algorîtmakî nayên çareser kirin ronî dike. Ev encam tevlihevî û nezelaliya xwerû di destnîşankirina tevgera hin pergalên de destnîşan dike, ku di sêwirandin û analîzkirina pergalên ewledar de girîngiyek girîng e.
Pirsgirêka zimanê vala di çarçoweya ewlehiya sîber de bi pirsa gelo TM ti rêzek qebûl dike ve girêdayî ye. Ew di qadê de pirsek bingehîn e ji ber ku ew li ser têgehên bingehîn ên teoriya tevliheviya hesabkerî û biryardariyê disekine. Neçareseriya pirsgirêka zimanê vala balê dikişîne ser tixûbên hesabkirinê û hebûna pirsgirêkên ku bi algorîtmîkî nayên çareser kirin, ku ev yek ji bo ewlehiya sîber bandorek girîng heye.
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