Ma her makîneya Turing a pir-tape makîneyek Turing-a yek-tape wekhev heye?
Pirsa ka gelo her makîneya Turing a pir-tape xwedan makîneyek Turing a yek-tape ya hevwate ye di warê teoriya tevliheviya hesabkirinê û teoriya hesabkirinê de girîng e.
Bersiv erê ye: her makîneya Turing a pir-tape bi rastî dikare ji hêla makîneyek Turing a yek-tape ve were simul kirin. Ev wekhevî ji bo têgihîştina hêza hesabker a makîneyên Turing û çînên pirsgirêkên ku ew dikarin çareser bikin girîng e.
Makîneya Turing, wekî ku di eslê xwe de ji hêla Alan Turing ve hatî fikirîn, modelek teorîkî ya hesabkirinê ye ku ji kasetek bêdawî, serê kasetek ku sembolên li ser kasêtê dixwîne û dinivîse, û komek hûrgelên rewşan ên ku kiryarên makîneyê li ser bingeha rewşa heyî û sembola ku tê xwendin. Makîneyek Turing a pir-tape vê modelê bi tevlihevkirina gelek kasetan, her yek bi serê xwe, dirêj dike. Ev pêvek dikare hin hesaban bikêrtir bike bi rêdana gihîştina hevdemî li beşên cihêreng ên têketinê û encamên navîn.
Ji bo têgihîştina wekheviya di navbera makîneyên Turing ên pir-tape û yek-tape de, pêdivî ye ku meriv pêvajoya simulasyonê binirxîne. Fikra sereke ev e ku makîneyek Turing a yek-tape dikare tevgera makîneyek Turing a pir-tape bi şîfrekirina naveroka hemî kasetan û pozîsyonên hemî serê kasêtan li ser yek kasêtek simule bike.
Makîneyeke Turing a pir-tape ya bi kasetên (k) bihesibînin. Her kasetek dikare wekî rêzek bêdawî ya hucreyan were hesibandin, ku her yek ji alfabeyek bêdawî nîşanek heye. Di makîneyê de (k) serê kaset, yek ji bo her kasetekê, û komek statûyek bêdawî heye. Fonksiyona veguheztinê li ser bingeha rewşa heyî û sembolên di bin serê her kasetê de kiryarên makîneyê diyar dike.
Ji bo ku em vê makîneya pir-tepe bi makîneya yek-tepe re simule bikin, pêdivî ye ku em naveroka hemî (k) kasetan û pozîsyonên (k) serê kasetan li ser kasetek tenê temsîl bikin. Nêzîkatiyek hevpar ev e ku meriv nexşeyek kodkirina taybetî bikar bîne. Mînakî, em dikarin nîşanek veqetandî bikar bînin da ku naveroka kasetên cihêreng û nîşankerên din ji hev veqetînin da ku cîhên serê kasetan destnîşan bikin.
Werin em alfabeya makîneya Turing a pir-tape bi ( Sigma ) destnîşan bikin û nîşanek veqetandî ya taybetî ( # ) ku ne di ( Sigma ) de ye destnîşan bikin. Dûv re em dikarin naveroka kasetên ( k ) li ser kasetek bi vî rengî nîşan bidin:
[# w_1 # w_2 # cdots # w_k # ]Li vir, (w_i) naveroka kaseta (i)-th temsîl dike. Ji bo nîşankirina pozîsyonên serê kasêtan, em dikarin cotek nîşanan bikar bînin da ku pozîsyona her serî nîşan bidin. Mînakî, heke serê li ser kasêta ( i ) -mîn nîşana ( j )-ê ya ( w_i ) dixwîne, em dikarin vê nîşan bikin bi danîna nîşanek taybetî, bêje (uparrow), berî (j)- sembola (w_i).
Ji ber vê yekê, kasetek yekane dibe ku bi vî rengî xuya bike:
[ # a_1 cdots a_{j-1} uparrow a_j cdots a_m # b_1 cdots b_n # cdots # c_1 cdots c_p # ]Di vê temsîlê de, (a_1 cdots a_m) naveroka kaseta yekem in, bi serê xwe li ber (a_j) tê danîn; (b_1 cdots b_n) naveroka kaseta duyemîn in, û hwd.
Pêdivî ye ku fonksiyona veguheztina makîneya Turing ya yek-tape were sêwirandin ku tevgera makîneya pir-tape simule bike. Ev çend gavan pêk tîne:
1. Xwendina Sembolan: Divê makîneya yek-tape sembolan di bin her serê kasetek simulkirî de bixwîne. Ew vê yekê bi şopandina kasêtê ji destpêkê ve û nîşankirina sembolên li dû her nîşankerê (li jor) dike.
2. Nûvekirina dewletê: Li ser bingeha rewşa heyî û sembolên xwendinê, makîneya yek-tape li gorî fonksiyona veguherîna makîneya pir-tepe rewşa xwe nû dike.
3. Sembolên Nivîsandinê: Makîneya yek-tepe sembolên nû li ser kasetên simulkirî dinivîse. Ew vê yekê bi şopandina kasêtê ji nû ve dike û sembolên li dû her nîşankerê (li jor) bi sembolên nû diguhezîne.
4. Seran dihejînin: Makîneya yek-tepe serê kasetên simulated dihejîne. Ev tê de guheztina nîşankerên (li jor) ber bi çep an rastê ve, wekî ku ji hêla fonksiyona veguherîna makîneya pir-tape ve hatî destnîşan kirin.
5. Dubarekirina Pêvajoyê: Makîneya yek-tape ji bo her veguheztina makîneya pir-tape vê pêvajoyê dubare dike.
Ev simulasyon dikare bi destnîşankirina fonksiyonek veguheztinê ya fermî ya ji bo makîneya yek-tape ya ku tevgera makîneya pir-tape-ê teqlîd dike rast were çêkirin. Têgihîştina sereke ev e ku dema ku makîneya yek-tape dibe ku bêtir gavan hewce bike da ku heman hesaban pêk bîne (ji ber hewcedariya şopandina kasêtê û nûvekirina nîşankeran), ew dikare tevgera makîneya pir-tape tam simule bike.
Ji bo ronîkirina vê yekê bi mînakek berbiçav, makîneyek Turing a 2-tape binihêrin ku peywira jêrîn pêk tîne: li ser kasêta yekem rêzek têketinê (w) tê dayîn, ew (w) li kaseta duyemîn kopî dike. Fonksiyona veguherînê ya ji bo makîneya 2-tape dibe ku bi vî rengî xuya bike:
1. Nîşana yekem a kaseta yekem bixwînin.
2. Li ser kasêta duyemîn heman sembolê binivîsin.
3. Serî li ser kaseta yekem ber bi rastê ve bihejînin.
4. Serî li ser kaseta duyemîn ber bi rastê ve bihejînin.
5. Dubare bike heta ku dawiya string input gihîşt.
Ji bo ku vê yekê bi makîneya Turing a yek-tape simule bikin, em du kasetên li ser kasetek yekane bi veqetandek (#) û nîşankeran (uparrow) temsîl dikin:
[# w uparrow # uparrow ]Fonksiyona veguhêz a makîneya yek-tepeyê dê di kasêtê de bişopîne da ku nîşankeran (li jor) bibîne, nîşana di binê nîşankera yekem de bixwîne, wê li dû nîşankera duyemîn binivîsîne, û dûv re cîhên nîşankeran nûve bike. Pêdivî ye ku makîneya yek-tape bi paş û paş ve bişopîne, lê ew ê di dawiyê de heman peywirê pêk bîne.
Ev simulasyon destnîşan dike ku her hesabek ku ji hêla makîneya Turing a pir-tape ve hatî çêkirin dikare ji hêla makîneya Turing-a yek-tape ve were kirin, her çend bi zêdebûna potansiyel a hejmara gavên pêwîst be. Ev zêdebûn bi gelemperî di hejmara gavên makîneya pir-tape de pirnomî ye, tê vê wateyê ku makîneya yek-tape herî zêde bi pirnomî hêdîtir e.
Wekheviya makîneyên Turing ên pir-tepe û yek-tape ji bo teoriya tevliheviya hesabkirinê bandorên girîng hene. Ew nîşan dide ku çîna zimanên ku ji hêla makîneyên Turing ve têne biryardan (çîna zimanên paşveger) û çîna zimanên ku ji hêla makîneyên Turing ve têne nas kirin (çîna zimanên ku bi vegerî têne hejmartin) ji hejmara kasetan nayên bandor kirin. Ev hevwate di heman demê de teza Church-Turing jî piştgirî dike, ku destnîşan dike ku her fonksiyonek bi bandorker dikare ji hêla makîneya Turing ve were hesibandin.
Wekî din, ev wekhevî ji bo têgihîştina çînên tevliheviyê yên wekî P (dema pirnomî) û NP (dema pirnomî ya ne-deterministic) bingehîn e. Simulasyona makîneyên Turing-a pir-tape-ê ji hêla makîneyên Turing-ê yên yek-tape ve piştrast dike ku ev çînên tevliheviyê, bêyî ku modela taybetî ya hesabkirinê tê bikar anîn, baş diyarkirî û bi hêz bimînin.
Her makîneya Turing a pir-tape dikare ji hêla makîneyek Turing-a yek-tape wekhev ve were simulasyon kirin. Ev hevsengî xurtbûna modela makîneya Turing û rola wê ya navendî di teoriya hesabkirinê de destnîşan dike. Pêvajoya simulasyonê, digel ku potansiyel hejmara gavên hewce zêde dike, kapasîteyên bingehîn ên hesabkirinê yên makîneyê diparêze.
Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:
- Bi berçavgirtina PDA-yên ne-determînîst, lihevkirina dewletan ji hêla pênasê ve gengaz e. Lêbelê, PDA-yên ne-determînîst tenê stekek heye ku nekare bi hevdemî di gelek dewletan de be. Ev çawa gengaz e?
- Mînaka PDA-yan çi ye ku ji bo analîzkirina seyrûsefera torê û nasîna qalibên ku binpêkirinên ewlehiyê yên potansiyel destnîşan dikin tê bikar anîn?
- Wateya wê çi ye ku zimanek ji yê din bi hêztir e?
- Ma zimanên hesas ên kontekstê ji hêla Makîneya Turing ve têne nas kirin?
- Çima ziman U = 0^n1^n (n>=0) ne rêkûpêk e?
- Meriv çawa FSM rêzikên binary bi hêjmarên '1' yên zewac nas dike pênase bike û nîşan bide ku dema ku rêzika têketinê 1011 hildiweşîne çi diqewime?
- Nedetermînîzm çawa bandorê li fonksiyona veguherînê dike?
- Ma zimanên birêkûpêk bi Makîneyên Dewleta Dawî re hevwate ne?
- Ma pola PSPACE ne bi pola EXPSPACE re wekhev e?
- Li gorî Teza Church-Turing pirsgirêka ku ji hêla algorîtmîkî ve tê hesibandin pirsgirêkek e ku ji hêla Makîneyek Turing ve tê hesibandin?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin