Teza Church-Turing çi ye û ew hesabkeriyê çawa diyar dike?
Teza Church-Turing di warê teoriya tevliheviya hesabkerî de têgehek bingehîn e, ku di têgihîştina sînorên hesabkirinê de rolek girîng dilîze. Navê wê ji matematîkzan Alonzo Church û mantiqzan û zanyarê kompîturê Alan Turing, ku di salên 1930-an de bi awayekî serbixwe ramanên bi vî rengî pêk anîne, hatiye binavkirin.
Di bingehê xwe de, Teza Church-Turing diyar dike ku her fonksiyonek ku bi bandor tête hesibandin dikare ji hêla makîneyek Turing ve were hesibandin. Bi gotineke din, heke fonksiyonek bi algorîtmayekê were hesibandin, wê hingê ew dikare ji hêla makîneya Turing ve jî were hesibandin. Ev tez tê vê wateyê ku têgîna hesabkeriyê di nav modelên cûda yên hesabkirinê de, wek makîneyên Turing, hesabê lambda, û fonksiyonên vegerî, wekhev e.
Makîneya Turing modelek matematîkî ya razber a komputerê ye ku ji kasetek bêdawî ku di nav şaneyan de hatî dabeş kirin, serê xwendin-nivîsandinê ku dikare li ser kasêtê bimeşîne, û yekîneyek kontrolê ya ku tevgera makîneyê diyar dike pêk tê. Kaset di destpêkê de vala ye, û tevgera makîneyê ji hêla komek rewş û qaîdeyên veguheztinê ve tê destnîşankirin. Makîne dikare nîşana li ser şaneya kasetê ya heyî bixwîne, nîşanek nû binivîse, serê xwe çep an rast biguhezîne û li gorî rewşa heyî û nîşana xwendinê rewşa xwe biguhezîne.
Teza Church-Turing destnîşan dike ku her fonksiyonek ku bi algorîtmayek were hesibandin dikare ji hêla makîneya Turing ve were hesibandin. Ev tê vê wateyê ku heke ji bo çareserkirina pirsgirêkek pêvajoyek gav-gav hebe, wê hingê makîneyek Turing heye ku dikare heman gavan pêk bîne. Berevajî vê, heke pirsgirêkek bi makîneya Turing neyê çareser kirin, wê hingê algorîtmayek ku bikaribe wê çareser bike tune.
Teza Church-Turing ji bo qada teoriya tevliheviya hesabkirinê xwedî bandorên girîng e. Ew ji bo têgihîştina sînorên hesabkirinê bingehek teorîkî peyda dike û alîkariya dabeşkirina pirsgirêkan li ser bingeha dijwariya wan a hesabkirinê dike. Mînakî, pirsgirêkên ku ji hêla makîneya Turing ve di dema pirnomîal de têne çareser kirin, wekî ji pola P (dema pirnomîal) têne dabeş kirin, lê pirsgirêkên ku hewcedariya wan bi wextê vekêşanê heye, wekî yên çîna EXP (dema berfirehî) têne dabeş kirin.
Digel vê yekê, Teza Church-Turing di warê ewlehiya sîber de encamên pratîkî hene. Ew di analîzkirina ewlehiya algorîtma û protokolên krîptografî de bi peydakirina çarçoveyek ji bo nirxandina pêkaniya hesabkerî ya êrîşan re dibe alîkar. Mînakî, heke algorîtmayek krîptografîk were îsbat kirin ku li hember êrişên makîneyek Turing ewledar e, ew di berxwedana xwe ya li hember êrişên pratîkî de pêbaweriyê peyda dike.
Teza Church-Turing di teoriya tevliheviya hesabkerî de têgehek bingehîn e ku wekheviya hesabkirinê di nav modelên cûda yên hesabkirinê de destnîşan dike. Ew diyar dike ku her fonksiyonek bi bandor a hesabkirî dikare ji hêla makîneya Turing ve were hesibandin. Ev tez ji bo têgihîştina sînorên hesabkirinê xwedî bandorên kûr e û di warê ewlehiya sîber de sepanên pratîkî hene.
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