Di teoriya tevliheviya hesabkerî de, lemma û encam di sazkirin û têgihiştina teoreman de rolek girîng dileyzin. Van avahîyên matematîkî têgihiştin û delîlên din peyda dikin ku encamên sereke piştgirî dikin, ji bo avakirina bingehek zexm ji bo analîzkirina tevliheviya pirsgirêkên hesabkirinê.
Lema encamên navber an pêşniyarên alîkar in ku rast têne îsbat kirin û ji bo îsbatkirina teoremên girîngtir wekî kevirên gav têne bikar anîn. Ew bi gelemperî raman an taybetmendiyên sereke yên ku ji bo têgihiştin û çareserkirina pirsgirêkên tevlihev girîng in digirin. Lema dikarin ji teoremên berê hatine damezrandin an jî serbixwe bêne îsbat kirin. Bi veqetandina pirsgirêkên tevlihev li beşên piçûktir, birêkûpêk, lemma rê dide lêkolîneran ku bala xwe bidin ser aliyên taybetî û analîza giştî hêsan bikin.
Ji aliyê din ve, encamên rasterast ên teoreman in. Ew bi karanîna dakêşên mentiqî yên ji encamên sereke têne derxistin û sepanên tavilê an dirêjkirina teoriyan peyda dikin. Encam bi gelemperî ji teoreman bi xwe hêsantir têne îsbat kirin, ji ber ku ew xwe dispêrin encamên ku berê hatine destnîşan kirin. Ew ji bo ronîkirina pêvek û encamên din ên teoremên sereke dixebitin, ji bo berfirehkirina têgihiştina pirsgirêka di dest de dibin alîkar.
Têkiliya di navbera lemma, hevok û teoreman de dikare bi avahiyek hiyerarşîk ve were hesibandin. Teorem asta herî bilind a girîngiyê temsîl dikin û encamên sereke ne ku lêkolîner armanc dikin ku îsbat bikin. Lema bi peydakirina encamên navîn piştgirîya teoreman dikin, dema ku hevpeyivîn encamên teoreman dirêj dikin. Bi hev re, van her sê pêkhateyan çarçoveyek hevgirtî ji bo analîzkirin û têgihiştina tevliheviya pirsgirêkên hesabkirinê pêk tînin.
Ji bo ronîkirina vê pêwendiyê, em mînakek di warê teoriya tevliheviya hesabkirinê de binirxînin. Teoremayek naskirî Teorema Hiyerarşiya Demê ye, ku dibêje ji bo her du fonksiyonên ku dem-avakirî f(n) û g(n), ku f(n) ji g(n) piçûktir e, zimanek heye ku dikare di wextê O(g(n)) de biryar bê dayîn lê ne di wextê O(f(n)). Ev teorem ji bo têgihiştina tevliheviya demê ya pirsgirêkên hesabkerî bandorên girîng hene.
Ji bo îsbatkirina Teorema Hiyerarşiya Demê, lêkolîner dikarin lemmayên ku hebûna hin cûreyên zimanan bi tevliheviyên demê yên taybetî destnîşan dikin bikar bînin. Mînakî, ew dikarin lemmayek îspat bikin ku hebûna zimanek destnîşan dike ku ji bo biryardanê bi kêmî ve demek berbiçav hewce dike. Ev lemma encamek navîn peyda dike ku teorema sereke piştgirî dike bi nîşandana hebûna pirsgirêkek ku bi bandor nayê çareser kirin.
Ji Teorema Hiyerarşiya Demê, lêkolîner dikarin encamên ku encamên taybetî yên teoremê ronî dikin derxînin. Mînakî, ew dikarin encamek derxînin ku hebûna pirsgirêkên ku ji bo çareserkirina wan wexta superpolînomî hewce dike nîşan dide, lê dîsa jî biryardar in. Ev encam encamên teoremê dirêj dike û di derheqê perestgeha tevliheviyê de nihêrînên din peyda dike.
Lemma û encam hêmanên bingehîn ên teoriya tevliheviya hesabkirinê ne. Lema wek encamên navbirî xizmetê dikin ku teoreman piştgirî dikin bi perçekirina pirsgirêkên tevlihev li beşên piçûktir. Encam, ji hêla din ve, encamên rasterast ên teoreman in û serlêdan an dirêjkirina tavilê peyda dikin. Bi hev re, van avahiyên matematîkî çarçoveyek hiyerarşîk ava dikin ku rê dide lêkolîneran ku tevliheviya pirsgirêkên hesabkirinê analîz bikin û fêm bikin.
Pirs û bersivên din ên vê dawiyê di derbarê EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê:
- 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?
- 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?
- Ma her pirsgirêkek kêfî dikare wekî zimanek were vegotin?
- Ma pola tevliheviya P binkomek pola PSPACE ye?
- Ma her makîneya Turing a pir-tape makîneyek Turing-a yek-tape wekhev heye?
- Berhemên predîkatan çi ne?
- Ma hesabên lambda û makîneyên turing modelên hesabker in ku bersivê didin pirsa ku tê çi wateyê?
- Ma em dikarin îsbat bikin ku çîna Np û P yek in bi dîtina çareseriyek polînomî ya bikêr ji bo her pirsgirêkek bêkêmasî ya NP li ser TM-ya diyarker?
Pirs û bersivan bêtir li Bingehên Teoriya Tevliheviya Hesabkirinê ya EITC/IS/CCTF bibînin