Di warê teoriya tevliheviya hesabkirinê de, destnîşankirina ka du algorîtma heman peywirê pêk tînin pirsgirêkek nediyar e. Ev tê vê wateyê ku algorîtmayek an prosedurek gelemperî tune ku her gav dikare diyar bike ka du algorîtma di warê karên ku ew dikin de wekhev in. Di vê bersivê de, em ê pêvajoya berhevdana du algorîtmayan diyar bikin û rave bikin ka çima ev pirsgirêk neçar e.
Ji bo berhevdana du algorîtmayan, pêdivî ye ku em tevgerên wan analîz bikin û diyar bikin ka ew ji bo hemî danûstendinên gengaz heman encaman derdixin. Nêzîkatiyek hevpar ev e ku meriv wekheviya makîneyên Turing bikar bîne, ku modelek teorîkî ya hesabkirinê ye ku têgeha hesabkirina algorîtmîkî digire. Makîneyên Turing ji kasetek, serê xwendin-nivîsandinê û komek rewşan pêk tên û ew dikarin li ser bingeha rewşa xwe ya heyî û sembola di binê serê xwendin-nivîsandinê de karên cihêreng li ser kasêtê bikin.
Ji bo berhevdana du algorîtmayên ku makîneyên Turing bikar tînin, em dikarin du makîneyên Turing ku algorîtmayên navborî temsîl dikin ava bikin. Divê van makîneyên Turing xwedî heman alfabeyên ketin û derketinê bin, û divê ew tevgera algorîtmayan li ser hemî têketinên gengaz simul bikin. Ger du makîneyên Turing ji bo hemî têketinê heman encam derxînin, em dikarin encam bidin ku algorîtma heman peywirê pêk tînin.
Lêbelê, destnîşankirina ka du makîneyên Turing wekhev in pirsgirêkek neçar e. Ev tê vê wateyê ku algorîtmayek tune ku her gav bikaribe diyar bike ka du makîneyên Turing ji bo hemî têketinê heman encam hilberînin. Belgeya vê encamê li ser bingeha têgeha pirsgirêka rawestanê ye, ku diyar dike ku algorîtmayek tune ku bikaribe diyar bike ka makîneyek Turing a diyar li ser têketinek diyar disekine.
Ji bo ku hûn bibînin ka çima pirsgirêka berhevdana du algorîtmayan neçar e, senaryoya jêrîn bifikirin. Bifikirin ku em du algorîtmayên A û B hene, û em dixwazin diyar bikin ka ew heman peywirê dikin. Em dikarin du makîneyên Turing TA û TB ava bikin ku bi rêzdarî tevgerên A û B simule dikin. Ger algorîtmayek hebe ku dikare biryarê bide ka TA û TB wekhev in, em dikarin wê bikar bînin da ku pirsgirêka sekinandinê çareser bikin. Bi taybetî, em dikarin makîneyek Turing TH ava bikin ku tevgera makîneya Turing a diyar T li ser têketina I-ya diyarkirî simule dike, û heke T li ser I raweste û wekî din "loop" vedigerîne. Bi karanîna algorîtmaya hîpotezîkî ya ji bo berhevdana makîneyên Turing, em dikarin diyar bikin ka TH û makîneya Turing a ku her gav li ser hemî têketinan disekine hevwate ne. Ger ew hevwate bin, ev tê wê wateyê ku TH li ser I disekine; Wekî din, ev tê vê wateyê ku TH li ser I-yê diqelişe. Ev nakokbariya pirsgirêka sekinandinê berovajî dike, îsbat dike ku pirsgirêka berhevdana du algorîtmayan neçar e.
Berawirdkirina du algorîtmayan ji bo destnîşankirina ka ew heman peywirê dikin pirsgirêkek nediyar e. Her çend em dikarin ji bo vê berhevdanê wekheviya makîneyên Turing wekî çarçoveyek teorîkî bikar bînin, algorîtmayek gelemperî tune ku her gav biryarê bide ka du algorîtma wekhev in. Ev encam li ser bêçareseriya pirsgirêka rawestandinê û rastiya ku pirsgirêka berhevdana makîneyên Turing bi pirsgirêka sekinandinê re kêm dibe.
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