Di çarçoveya teoriya tevliheviya hesabkerî de têgeha biryardarbûnê çi ye?
Biryardarbûn, di çarçoweya teoriya tevliheviya hesabkerî de, jêhatîbûnê vedibêje ka gelo pirsgirêkek diyarkirî dikare bi algorîtmayek were çareser kirin. Ew têgehek bingehîn e ku di têgihîştina sînorên hesabkirinê û dabeşkirina pirsgirêkan de li ser bingeha tevliheviya wan a hesabkirinê de rolek girîng dilîze.
Di teoriya tevliheviya hesabkirinê de, pirsgirêk bi gelemperî li ser bingeha çavkaniyên ku ji bo çareserkirina wan hewce ne li çînên tevliheviya cûda têne dabeş kirin. Di van çavkaniyan de dem, cîh û çavkaniyên din ên hesabkirinê hene. Têgeha biryardarbûnê li ser pirsa gelo pirsgirêkek bi tevahî dikare were çareser kirin, bêyî ku çavkaniyên pêwîst be, disekine.
Ji bo danasîna fermî ya biryardariyê, pêdivî ye ku em têgîna pirsgirêkek biryarê bidin nasîn. Pirsgirêka biryarê pirsgirêkek e ku bersivek erê an na heye. Mînakî, pirsgirêka destnîşankirina ka hejmareke diyarkirî ya yekem e pirsgirêkek biryarê ye. Jimara têketinê tê dayîn, pirsgirêk dipirse gelo hejmar yekem e an na, û bersiv dikare erê an na be.
Biryardarbûn bi destnîşankirina ka pirsgirêkek biryarê dikare bi algorîtmayek ve were çareser kirin, an jî bi heman rengî, gelo makîneyek Turing heye ku dikare pirsgirêkê çareser bike ve girêdayî ye. Makîneya Turing modelek teorîkî ya hesabkirinê ye ku dikare her algorîtmayê simule bike. Ger pirsgirêkek biryarê bi makîneyek Turing ve were çareser kirin, tê gotin ku ew biryardar e.
Bi fermî, heke makîneyek Turing hebe ku li ser her têketinê disekine û bersiva rast çêdike, pirsgirêkek biryarê biryardar e. Bi gotinek din, ji bo her mînakek pirsgirêkê, makîneya Turing dê di dawiyê de bigihîje rewşek rawestanê û bersiva rast derxe (an erê an na).
Biryardarbûn ji nêz ve bi têgeha hesabkeriyê ve girêdayî ye. Pirsgirêkek biryardar e ger û tenê heke ew hesabker be, tê vê wateyê ku algorîtmayek heye ku dikare pirsgirêkê çareser bike. Lêkolîna biryardarbûn û hesabkirinê di derheqê sînorên ku meriv dikare were hesibandin de têgihiştinan peyda dike û di têgihîştina sînorên tevliheviya hesabkirinê de dibe alîkar.
Ji bo ronîkirina têgîna biryardarbûnê, werin em pirsgirêka destnîşankirina ka rêzek diyar palindrom e an na. Palindrom xêzek e ku bi pêş û paş ve yeksan dixwîne. Mînakî, "racecar" palindromek e. Pirsgirêka biryarê ya ku bi palindroman ve girêdayî ye dipirse gelo rêzek diyar palindrom e an na.
Pirsgirêka vê biryarê biryardar e ji ber ku algorîtmayek heye ku dikare wê çareser bike. Yek algorîtmayek gengaz ev e ku meriv tîpên yekem û paşîn ên rêzikê, dûv re tîpên duyemîn û duyemîn-paşîn, û hwd. Ger di her xalê de tîpan li hev nekin, algorîtma dikare encam bide ku rêz ne palindromek e. Ger hemî tîpan li hev bikin, algorîtma dikare encam bide ku string palindromek e.
Di çarçoweya teoriya tevliheviya hesabkerî de biryardarbûn qabiliyeta ku diyar bike ka pirsgirêkek diyarkirî dikare bi algorîtmayek were çareser kirin vedibêje. Pirsgirêkek biryardar e heke makîneyek Turing hebe ku dikare wê çareser bike, tê vê wateyê ku makîne li ser her têketinê disekine û bersiva rast dide. Biryardarbûn têgehek bingehîn e ku di têgihîştina sînorên hesabkirinê û dabeşkirina pirsgirêkan de li ser bingeha tevliheviya wan a hesabkirinê dibe alîkar.
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