Têgeha kêmbûnê û rola wê ya di îsbatkirina nebiryarbûnê de rave bike.
Kêmkirin di teoriya tevliheviya hesabkerî de têgehek bingehîn e ku di îsbatkirina neçareseriyê de rolek girîng dilîze. Ew teknîkek e ku tê bikar anîn da ku bêçareseriya pirsgirêkek bi kêmkirina wê berbi pirsgirêkek nediyarkirî ya naskirî ve saz bike. Di eslê xwe de, kêmbûnî dihêle ku em nîşan bidin ku ger me algorîtmayek ji bo çareserkirina pirsgirêka navborî hebûya, em dikarin wê bikar bînin da ku pirsgirêka nediyarkirî ya naskirî çareser bikin, ku ev nakokî ye.
Ji bo têgihîştina kêmbûnê, em pêşî têgîna pirsgirêkek biryarê diyar bikin. Pirsgirêka biryarê pirsgirêkek hesabker e ku bersivek erê/na hewce dike. Mînakî, pirsgirêka destnîşankirina ka hejmareke diyar yekem e an pêkhatî ye pirsgirêkek biryarê ye. Em dikarin pirsgirêkên biryarê wekî zimanên fermî temsîl bikin, ku têlên di zimên de nimûneyên ku bersiva wan "erê" ye.
Naha, werin em du pirsgirêkên biryarê, P û Q bihesibînin. Em dibêjin ku P bi Q tê kêmkirin (wek P ≤ Q tê destnîşan kirin) heke fonksiyonek hejmarbar f hebe ku mînakên P-yê veguherîne mînakên Q bi vî rengî ku bersiv hebe. ji bo mînakek x-ya P-yê "erê" ye ger û tenê heke bersiva f(x) ya Q-yê "erê" be. Bi gotineke din, f bersiva pirsgirêkê diparêze.
Fikra bingehîn a li paş kêmbûnê ev e ku heke em karibin pirsgirêka P-yê bi pirsgirêka Q kêm bikin, wê hingê Q bi kêmanî bi qasî P-yê dijwar e. Ger me algorîtmayek ji bo çareserkirina Q-yê hebûya, em dikarin wê, digel fonksiyona kêmkirina f, ji bo çareserkirinê bikar bînin. P. Ev tê wê wateyê ku ger Q nebiryar be, wê demê divê P jî nebiryar be. Bi vî rengî, kêmbûn rê dide me ku em neçarî "veguhezînin" ji pirsgirêkek din.
Ji bo îsbatkirina bêçareseriyê bi karanîna kêmbûnê, em bi gelemperî bi pirsgirêkek nediyarkirî ya naskirî dest pê dikin, wek Pirsgirêka Halting, ku dipirse gelo bernameyek diyar li ser têketinek diyar disekine. Dûv re em destnîşan dikin ku heke me algorîtmayek ji bo çareserkirina pirsgirêka me ya balkêş hebe, em dikarin wê ji bo çareserkirina Pirsgirêka Haltingê bikar bînin, ku berbi nakokî ve bibe. Ev bêçareseriya pirsgirêka me destnîşan dike.
Mînakî, werin em pirsgirêka destnîşankirina ka bernameyek diyar P ti têketinê qebûl dike an na. Em dikarin Pirsgirêka Haltingê bi vê pirsgirêkê kêm bikin bi avakirina fonksiyona kêmkirinê f ku bernameyek Q û têketinek x wekî têketinê digire, û bernameyek P-ya ku wiha tevdigere derdixe: heke Q li ser x raweste, wê demê P her têketinê qebûl dike; Wekî din, P ji bo her têketinê têkeve xelekek bêdawî. Ger me algorîtmayek ji bo çareserkirina pirsgirêka ku diyar bike ka P têketinek qebûl dike hebe, em dikarin wê ji bo çareserkirina Pirsgirêka Haltingê bi karanîna wê li f(Q, x) bikar bînin. Ji ber vê yekê, pirsgirêka destnîşankirina ka bernameyek her têketinê qebûl dike ne diyar e.
Kêmkirin di teoriya tevliheviya hesabkerî de teknîkek hêzdar e ku destûrê dide me ku em neçarîbûna pirsgirêkê bi kêmkirina wê di pirsgirêkek nediyarkirî ya naskirî de îspat bikin. Bi danîna kêmkirina ji pirsgirêkek P-yê ber bi pirsgirêkek Q ve, em destnîşan dikin ku Q bi kêmanî bi qasî P-yê dijwar e, û heke Q nebiryar be, wê hingê divê P jî nebiryar be. Ev teknîk me dihêle ku em neçarî di navbera pirsgirêkan de veguhezînin û ji bo têgihîştina sînorên hesabkirinê amûrek hêja peyda dike.
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