Ji bo pirsgirêka zimanê vala bi teknîka kêmkirinê îsbata bêçareseriyê rave bike.
Di teoriya tevliheviya hesabkerî de îsbata bêçareseriyê ji bo pirsgirêka zimanê vala bi karanîna teknîka kêmkirinê têgehek bingehîn e. Ev delîl nîşan dide ku ne mimkûn e ku meriv diyar bike ka makîneyek Turing (TM) rêzek qebûl dike an na. Di vê ravekirinê de, em ê hûrguliyên vê delîlê binirxînin, têgihîştinek berfireh a mijarê peyda bikin.
Ji bo destpêkê, werin em pirsgirêka zimanê vala diyar bikin. TM M-ya ku tê dayîn, pirsgirêka zimanê vala dipirse gelo zimanê ku ji hêla M ve hatî pejirandin vala ye, ango ti rêzikên ku M qebûl dike tune. Bi gotineke din, em dixwazin diyar bikin ka bi kêmanî yek rêzek heye ku M qebûl dike.
Ji bo îsbatkirina neçariya vê pirsgirêkê, em teknîka kêmkirinê bikar tînin. Kêmkirin di teoriya tevliheviya hesabkerî de amûrek hêzdar e ku destûrê dide me ku em neçarîbûna pirsgirêkek bi kêmkirina wê ji bo pirsgirêkek din a nediyar a naskirî nîşan bidin.
Di vê rewşê de, em pirsgirêka rawestandinê kêm bikin pirsgirêka zimanê vala. Pirsgirêka sekinandinê mînakek klasîk a pirsgirêkek nebiryar e, ku dipirse gelo TM-ya diyar li ser têketinek diyar disekine. Em dihesibînin ku pirsgirêka rawestandinê nayê çareser kirin û vê texmînê bikar tînin da ku bêçareserbûna pirsgirêka zimanê vala îspat bikin.
Kêmkirin wiha pêk tê:
1. Ji bo pirsgirêka rawestanê ketina (M, w) tê dayîn, TM M'ya nû bi vî rengî ava bikin:
– M' guh nade ketina xwe û M li ser w simule dike.
- Ger M li ser w bisekine, M' dikeve çerxeke bêdawî û qebûl dike.
– Ger M li ser w nesekine, M' disekine û red dike.
2. Niha, em îdia dikin ku (M, w) mînakek erênî ya pirsgirêka rawestanê ye ger û tenê heke zimanê ku ji hêla M' ve hatî pejirandin vala be.
- Ger (M, w) mînakek erênî ya pirsgirêka rawestanê be, ev tê wê wateyê ku M li ser w disekine. Di vê rewşê de, M' dikeve xelekek bêdawî û ti rêzan qebûl nake. Ji ber vê yekê zimanê ku M' qebûl kiriye vala ye.
– Berevajî vê, eger zimanê ku ji aliyê M'yê ve hatiye qebûlkirin vala be, ev tê wê wateyê ku M' tu rêzikan qebûl nake. Ev tenê dikare biqewime heke M li ser w nesekine, ji ber ku wekî din, M' dê têkeve dorpêkek bêdawî û ti rêzan qebûl neke. Ji ber vê yekê, (M, w) mînakek erênî ya pirsgirêka rawestandinê ye.
Ji ber vê yekê, me bi serfirazî pirsgirêka rawestandina bêçareseriyê daxist pirsgirêka zimanê vala. Ji ber ku tê zanîn ku pirsgirêka rawestandinê neçareser e, ev kêmkirin neçareserbûna pirsgirêka zimanê vala jî destnîşan dike.
Belgeya bêçareseriyê ji bo pirsgirêka zimanê vala bi karanîna teknîka kêmkirinê destnîşan dike ku ne gengaz e ku meriv diyar bike ka TM rêzek qebûl dike an na. Ev delîl xwe dispêre kêmkirina pirsgirêka rawestanê ber bi pirsgirêka zimanê vala ve, û hêza kêmkirinê di sazkirina bêçareseriyê de nîşan dide.
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