Lêpirsîna di derbarê ka gelo hemî cûrbecûr cûrbecûr makîneyên Turing di kapasîteya hesabkirinê de wekhev in pirsek bingehîn e di warê zanistiya computerê ya teorîkî de, nemaze di lêkolîna teoriya tevliheviya hesabkerî û biryarbûnê de. Ji bo çareserkirina vê yekê, pêdivî ye ku meriv cewherê makîneyên Turing û têgîna hevberdana hesabî bihesibîne.
Makîneya Turing modêlek matematîkî ya razber a hesabkirinê ye ku ji hêla Alan Turing ve di sala 1936-an de hate destnîşan kirin. Ew ji kasetek bêdawî, serê kasetek ku dikare sembolên li ser kasêtê bixwîne û binivîsîne, komek rewşan a dawî, û fonksiyonek veguhêz pêk tê. kiryarên makîneyê li ser bingeha rewşa heyî û sembola ku tê xwendin destnîşan dike. Makîneya Turing a standard, ku bi gelemperî wekî makîneya Turing "klasîk" an "yek-tape" tê binav kirin, ji bo pênasekirina pêvajoyên hesabkirinê wekî modela bingehîn kar dike.
Gelek guhertoyên makîneyên Turing hene, her yek bi veavakirin an pêşkeftinên cihêreng. Hin guhertoyên berbiçav hene:
1. Multi-tape Turing Machines: Van makîneyan gelek kaset û serê kasetên têkildar hene. Her kasetek serbixwe tevdigere, û fonksiyona veguherînê dikare bi sembolên ku ji hemî kasetan têne xwendin ve girêdayî be. Tevî tevliheviya zêde, makîneyên Turing-a pir-tape ji hêla hesabkirinê ve bi makîneyên Turing-a yek-tape re wekhev in. Ev tê vê wateyê ku her hesabek ku ji hêla makîneya Turing a pir-tape ve hatî çêkirin dikare ji hêla makîneyek Turing-yek-tape ve were simul kirin, her çend bi zêdebûna polînomî ya gengaz a hejmara gavên hewcedar be jî.
2. Makîneyên Turingê yên ne-determînîst (NTM): Van makîneyan dikarin ji bo rewşek diyarkirî û sembola têketinê gelek veguheztinan bikin, bi bandor li gelek riyên hesabkeriyê şax bibin. Digel ku NTM dikarin gelek rêçên hesabkerî bi hevdemî vekolin, ew di heman demê de ji hêla jimartinê ve bi makîneyên Turing ên diyarker (DTM) re jî hevwate ne. Her zimanek ku ji hêla NTM-ê ve hatî nas kirin dikare ji hêla DTM-ê ve jî were nas kirin, her çend dibe ku simulasyon di rewşa herî xirab de hewceyê demek berbiçav be.
3. Makîneyên Turingê yên Gerdûnî (UTM): UTM makîneyeke Turing e ku dikare her makîneyeke din a Turing simule bike. Ew danasîna makîneyeke din a Turing û rêzikek têketinê ji bo wê makîneyê wekî têketinê digire. Dûv re UTM tevgera makîneya diyarkirî li ser rêzika têketinê simul dike. Hebûna UTM-an destnîşan dike ku makîneyek yekane dikare hesabek ku her makîneyek din a Turing dikare dikare pêk bîne, gerdûnîbûna modela makîneya Turing ronî dike.
4. Makîneyên Turing bi Kasetên Nîv Bêdawî: Van makîneyan kasetên ku tenê di yek alî de bêsînor in hene. Ew ji hêla jimartinê ve bi makîneyên Turing standard re hevwate ne, ji ber ku her hesabek ku ji hêla makîneyek Turing ya nîv-bêsînor ve hatî çêkirin dikare ji hêla makîneyek Turing standard ve bi kodkirina guncan a naveroka kasêtê ve were simul kirin.
5. Makîneyên Turing bi Serên Pirjimar: Van makîneyan gelek serê kaset hene ku dikarin li ser yek kasetekê bixwînin û binivîsin. Mîna makîneyên Turingê yên pir-tape, makîneyên Turing-ê yên pir-serî ji hêla jimartinê ve bi makîneyên Turing-ê yên yek-tape re hevwate ne, digel ku simulasyon bi potansiyel gavên pêvek hewce dike.
6. Makîneyên Turing Alternatîf (ATM): Ev makîneyên hanê NTM-yan giştî dikin bi rê didin ku dewlet wekî hebûnî an gerdûnî bêne destnîşan kirin. ATM têketinek dipejirîne ger rêzek tevgerên ji rewşa destpêkê berbi rewşek pejirandî ve hebe ku şert û mercên hebûnî û gerdûnî têr dike. ATM di heman demê de ji hêla zimanên ku ew nas dikin ve ji hêla DTM-yan ve hevwate ne, her çend dersên tevliheviya ku ew diyar dikin, wek hiyerarşiya pirnomî, ji hev cûda dibin.
7. Makîneyên Turingê yên Quantum (QTM): Van makîneyan prensîbên mekanîka kuantûmê di nav xwe de dihewîne, rê dide serhevkirin û tevlihevkirina dewletan. Digel ku QTM dikarin hin pirsgirêkan ji makîneyên Turing ên klasîk bi bandortir çareser bikin (mînak, faktorkirina jimareyên mezin bi karanîna algorîtmaya Shor), ew di warê çîna fonksiyonên hesabker de ne bi hêztir in. Her fonksiyonek ku ji hêla QTM ve tê hesibandin jî ji hêla makîneya Turing a klasîk ve tê hesibandin.
Wekheviya guhertoyên cihêreng ên makîneya Turing di kapasîteya hesabkirinê de di Teza Church-Turing de bingeh e. Ev tez destnîşan dike ku her fonksiyonek ku ji hêla her modelek maqûl ya maqûl ve bi bandor were hesibandin dikare ji hêla makîneya Turing ve jî were hesibandin. Ji ber vê yekê, hemî cûrbecûrên jorîn ên makîneyên Turing di warê kapasîteya wan a hesabkirina fonksiyonan û naskirina zimanan de wekhev in, her çend ew di karîgerî an tevliheviya simulasyonê de cûda bibin.
Ji bo ronîkirina vê wekheviyê, karê simulasyona makîneya Turing a pir-tape bi karanîna makîneyek Turing a yek-tape binihêrin. Bifikirin ku me makîneyeke Turing a pir-tape ya bi kasetên (k) heye. Em dikarin vê makîneyê bi makîneya Turing a yek-tape simule bikin bi şîfrekirina naveroka hemî (k) kasetan li ser kasetek yekane. Kasêta makîneya yek-tepe dikare di beşên (k) de were dabeş kirin, ku her yek ji kasetên orîjînal temsîl dike. Rewşa makîneyê dikare agahdariya li ser pozîsyonên serê kasetan li ser her kasetek (k) bigire. Fonksiyona veguheztinê ya makîneya yek-tape dikare were sêwirandin ku bi nûvekirina naveroka kasêta kodkirî û pozîsyonên serî li gorî vê yekê behremendiya makîneya pir-tape bişibîne. Digel ku ev simulasyon ji makîneya pir-tape ya orjînal zêdetir gavan hewce dike, ew destnîşan dike ku makîneya yek-tape dikare heman hesabkirinê pêk bîne.
Bi heman rengî, simulasyona makîneyek Turing a ne-determînîst bi makîneyek Turing a diyarker ve bi rêkûpêk vekolîna hemî rêyên hesabker ên gengaz ên NTM-yê vedihewîne. Ev dikare bi karanîna teknolojiyên wekî lêgerîna yekem-fireh an lêgerîna pêşîn-kûrahî were bidestxistin, da ku piştrast bike ku hemî rê di dawiyê de têne lêkolîn kirin. Her çend dibe ku simulasyon bi rengek hêdî hêdî be jî, ew piştrast dike ku DTM dikare heman zimanan wekî NTM nas bike.
Gerdûnîbûna makîneyên Turing bi hebûna makîneyên gerdûnî yên Turing ve tê nimûne. UTM dikare makîneyek din a Turing bi şirovekirina ravekirina makîneya armanc û têketina wê simule bike. Vê kapasîteyê prensîba bingehîn radixe ber çavan ku modelek hesabkerî ya yekane dikare tevgera hemî modelên din vehewîne, têgîna wekheviya hesabkerî xurt bike.
Digel ku guhertoyên cihêreng ên makîneyên Turing dibe ku di warê karîgerî, hêsaniya bernamekirinê, an zelaliya têgehî de avantajên cihêreng peyda bikin, ew hemî di kapasîteya hesabkirinê de wekhev in. Ev wekhevî kevirê bingehîn ê zanistiya komputerê ya teorîkî ye, ji bo têgihîştina sînorên hesabkirinê û cewherê biryardariyê çarçoveyek yekgirtî peyda dike.
Pirs û bersivên din ên vê dawiyê di derbarê Fonksiyonên kêrhatî:
- Têkiliya di navbera fonksiyonek hesabker û hebûna makîneya Turing a ku dikare wê hesab bike vebêje.
- Wateya makîneya Turingê ya ku her dem dema ku fonksiyonek hesabker hesab dike disekine çi ye?
- Ma makîneyek Turing dikare were guheztin da ku her gav fonksiyonek qebûl bike? Vebêjin çima an çima na.
- Makîneya Turing fonksiyonek çawa hesab dike û rola kasetên ketin û derketinê çi ye?
- Di çarçoveya teoriya tevliheviya hesabkerî de fonksiyonek hesabker çi ye û ew çawa tête diyar kirin?