Ger du TM-yên me hene ku zimanek biryardar diyar dikin, gelo pirsa wekheviyê hîn jî nayê biryar?
Di warê teoriya tevliheviya hesabkirinê de, têgeha biryardarbûnê rolek bingehîn dilîze. Zimanek tê gotin ku biryardar e heke makîneyek Turing (TM) hebe ku dikare ji bo her têketinek diyar diyar bike ka ew ji zimên re ye an na. Biryardarbûna ziman taybetmendiyek girîng e, ji ber ku ew dihêle ku em li ser ziman û taybetmendiyên wî bi algorîtmîkî bifikirin.
Pirsa wekheviyê ji bo makîneyên Turing bi destnîşankirina ka du TM-yên dayîn heman zimanî nas dikin re têkildar e. Bi awayekî fermî, du TM-yên M1 û M2 têne dayîn, pirsa wekheviyê dipirse gelo L(M1) = L(M2), ku L(M) zimanê ku ji hêla TM M ve hatî nas kirin temsîl dike.
Pirsgirêka gelemperî ya destnîşankirina hevberdana du TM-yê wekî neçar e ku tê zanîn. Ev tê wê wateyê ku algorîtmayek tune ku her gav biryarê bide ka du TM-yên keyfî heman zimanî nas dikin an na. Ev encam ji hêla Alan Turing ve di xebata xwe ya girîng a li ser hesabkirinê de hate îsbat kirin.
Lêbelê, girîng e ku were zanîn ku ev encam ji bo rewşa gelemperî ya TM-yên kêfî digire. Di rewşa taybetî de ku her du TM zimanên biryardar rave dikin, pirsa wekheviyê biryardar dibe. Ev ji ber ku zimanên biryardar ew in ku ji bo wan TM heye ku dikare endamtiya di ziman de biryar bide. Ji ber vê yekê, heke du TM zimanên biryardar rave bikin, em dikarin TM-ya nû ava bikin ku wekheviya wan biryar dide.
Ji bo ronîkirina vê yekê, werin em mînakek bifikirin. Bifikirin ku me du TM M1 û M2 hene ku zimanên biryardar diyar dikin. Em dikarin TM M-ya nû ava bikin ku wekheviya wan wiha biryar dide:
1. Ji ketina x tê dayîn, M1 li ser x û M2 li ser x hevdemî simule bikin.
2. Ger M1 x-ê qebûl bike û M2 jî x-ê qebûl bike, wê hingê qebûl bike.
3. Ger M1 x red bike û M2 x red bike, paşê qebûl bike.
4. Wekî din, red bikin.
Ji hêla avakirinê ve, TM M dê têketinek x qebûl bike heke û tenê heke hem M1 û hem M2 x-yê qebûl bikin, an hem M1 û hem jî M2 x-yê red bikin. Ev tê vê wateyê ku M hevberdana M1 û M2 ji bo her têketina x-yê diyar dike.
Dema ku pirsgirêka giştî ya diyarkirina hevberdana du TM-yên keyfî nayê çareserkirin, heke TM zimanên biryardar rave bikin, pirsa hevwateyê dibe biryar. Ev ji ber ku zimanên biryardar dikarin ji hêla TM-yê ve bêne biryardan, rê dide me ku em TM-ya ku wekheviya wan biryar dide ava bikin. Çareserkirina pirsa wekheviyê ji bo TM-yên ku zimanên biryardar rave dikin, di derheqê tevliheviya hesabkerî ya van zimanan de nihêrînên girîng 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?
- 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?
- Pêvajoya veguhertina makîneyek Turing li komek çîpên ji bo PCP-ê vebêjin, û ka van pêlikan çawa dîroka hesabkirinê temsîl dikin.
Pir pirs û bersivan di Decidability de bibînin