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?
Teza Church-Turing di teoriya hesabkirin û tevliheviya hesabkirinê de prensîbek bingehîn e. Ew destnîşan dike ku her fonksiyonek ku ji hêla algorîtmayek ve were hesibandin dikare ji hêla makîneya Turing ve jî were hesibandin.
Ev tez ne teorema resmî ye ku were îsbatkirin; lêbelê, ew hîpotezek e li ser xwezaya fonksiyonên hesabker. Ew pêşniyar dike ku têgeha "hesibandina algorîtmîkî" bi têra xwe ji hêla makîneyên Turing ve tê girtin.
Makîneya Turing modelek matematîkî ya razber a hesabkirinê ye ku makîneyek îdealîzekirî diyar dike ku karibe her hesabek ku dikare bi algorîtmakî were diyar kirin pêk bîne. Ew ji kasetek bêdawî ya ku di nav şaneyan de hatî dabeş kirin, serê kasetek ku dikare sembolan li ser kasêtê bixwîne û binivîsîne, û komek halên dawî yên ku kiryarên makîneyê li gorî rewşa heyî û sembola tê xwendin diyar dikin pêk tê. Makîne li gorî komek rêgezan an fonksiyonek veguheztinê ya ku destnîşan dike ka ew çawa di navbera dewletan de dimeşe, sembolan dixwîne û dinivîse, û serê kasêtê diherike, dixebite.
Teza Church-Turing destnîşan dike ku heke pirsgirêkek bi her rêgezek hesabkerî were çareser kirin, wê hingê makîneyek Turing heye ku dikare wê pirsgirêkê çareser bike. Ev tez ji bo qada zanistiya komputerê bandorek kûr heye, ji ber ku ew çarçoveyek fermî peyda dike ji bo têgihîştina sînorên tiştê ku dikare were hesibandin.
Ji bo ronîkirina têgehê, pirsgirêka destnîşankirina ka stringek diyar palindrom e an na. Palindrom xêzek e ku bi pêş û paş ve yeksan dixwîne. Algorîtmayek ji bo çareserkirina vê pirsgirêkê dibe ku berawirdkirina tîpên yekem û paşîn ên rêzê, dûv re tîpên duyemîn û duyemîn-paşîn, û hwd, heya ku hemî karakter werin berhev kirin. Heke hemî tîpên têkildar li hev bikin, rêzik palindromek e; wekî din, ew nabe.
Ji bo çareserkirina vê pirsgirêkê makîneyek Turing dikare were çêkirin. Makîne dê dest bi xwendina karaktera yekem a rêzê bike û bi rengekî nîşan bide (mînak, bi nivîsandina nîşanek taybetî li ser wê). Dûv re ew ê derbasî dawiya rêzê bibe, karaktera paşîn bixwîne û bi karaktera yekem re bide ber hev. Ger ew li hev bikin, makîne dê karaktera paşîn nîşan bide û ji destpêkê ve vegere karaktera bênavber a din, pêvajoyê dubare bike heya ku hemî karakter werin berhev kirin. Ger di her xalê de karakter li hev nekin, makîne dê raweste û têketinê red bike. Ger hemî karakter li hev bikin, makîne dê raweste û têketinê qebûl bike.
Ev nimûne nîşan dide ku çawa pirsgirêkek ku bi algorîtmîkî ve tête diyar kirin jî dikare ji hêla makîneya Turing ve were çareser kirin, ku Teza Church-Turing piştgirî dike. Tez tê vê wateyê ku her pirsgirêkek hesabkerî ya ku bi algorîtmayek were çareser kirin, di prensîbê de, bi makîneyek Turing ve dikare were çareser kirin.
Di çarçoweya teoriya tevliheviya ewlekariya sîber û hesabkeriyê de, Teza Church-Turing ji bo têgihîştina sînorên tiştê ku dikare were hesibandin û çavkaniyên ku ji bo hesabkirina wê hewce ne xwedî bandorên girîng e. Teoriya tevliheviya hesabkirinê bi dabeşkirina pirsgirêkên hesabkirinê li ser bingeha dijwariya wan a cewherî û çavkaniyên (wekî dem û cîh) yên ku ji bo çareserkirina wan hewce ne re têkildar e. Tez bingehek ji bo vê dabeşkirinê peyda dike bi damezrandina çarçoveyek hevbeş ji bo destnîşankirin û berhevkirina hêza hesabker a modelên cûda yên hesabkirinê.
Di teoriya tevliheviya hesabkerî de yek têgehek girîng cûdahiya di navbera pirsgirêkên biryardar û nebiryar de ye. Ger makîneyek Turing hebe ku bikaribe wê di demek bêdawî de ji bo hemî têketinên gengaz çareser bike pirsgirêk çareser dibe. Ji hêla din ve, pirsgirêkek neçareser ew e ku makîneyek Turing a wusa tune. Pirsgirêka Rawestandinê, ku dipirse gelo makîneyek Turing a diyarkirî dê li ser têketinek diyar raweste, mînakek klasîk a pirsgirêkek neçareser e. Alan Turing îsbat kir ku tu algorîtmayek gelemperî tune ku bikaribe Pirsgirêka Haltingê ji bo hemî makîneyên Turing û têketinên gengaz çareser bike, û hebûna pirsgirêkên nehesabkirî yên xwerû destnîşan dike.
Teza Church-Turing di heman demê de bi têgîna vegerê ve girêdayî ye, ku teknîkek bingehîn e di zanistiya komputer û matematîkê de ji bo diyarkirina fonksiyonan û çareserkirina pirsgirêkan. Fonksiyonên vegerî ew in ku bi xwe têne diyar kirin, bi gelemperî bi bûyerek bingehîn ji bo bidawîkirina vegerê. Çîna fonksiyonên vegerî yên primitive, ku bi karanîna fonksiyonên bingehîn û pêkhatin û vegerandina seretayî têne destnîşan kirin, binkeyek ji çîna fonksiyonên vegerî yên gelemperî ye, ku hemî fonksiyonên ku dikarin ji hêla makîneya Turing ve bêne hesibandin vedihewîne.
Makîneya Turing a ku ji xwe re ravekek dinivîse, mînakek pergala xwe-referensî an xwe-berberkirinê ye, ku bi têgeha vegerê ve girêdayî ye. Makîneyek wusa, ku pir caran wekî quine tê binav kirin, bernameyek e ku kopiyek koda çavkaniya xwe wekî encamek xwe çêdike. Quines ji perspektîfek teorîkî ve balkêş in ji ber ku ew şiyana makîneyek Turing nîşan didin ku hesabên xwe-referansê pêk bîne, ku dikare ji bo têgihîştina sînorên hesabkirinê û xwezaya pergalên xwe-berberîberî bandor bike.
Teza Church-Turing ji bo têgihiştina cewhera hesabkirina algorîtmîkî û sînorên hesabkirinê çarçoveyek bingehîn peyda dike. Ew destnîşan dike ku her pirsgirêkek ku bi algorîtmayek were çareser kirin jî dikare ji hêla makîneya Turing ve were çareser kirin, ji bo berhevkirina modelên cûda yên hesabkirinê çarçoveyek hevbeş saz dike. Tez ji bo qada teoriya tevliheviya hesabkerî xwedî bandorên kûr e, ji ber ku ew bingehek ji bo dabeşkirina pirsgirêkên hesabkirinê û têgihîştina çavkaniyên ku ji bo çareserkirina wan hewce ne peyda dike. Têgeha makîneya Turing a ku ravekek ji xwe re dinivîse, hêza hesabkirina xwe-referansê û şiyana makîneyên Turing ji bo pêkanîna hesabên tevlihev, paşverû diyar dike.
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?
- Taybetmendiya girtina zimanên birêkûpêk ên di bin hevgirtinê de çi ye? Makîneyên dewleta dawîn çawa li hev tên ku yekbûna zimanan bi du makîneyan tê naskirin temsîl bikin?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin