Têkiliya di navbera fonksiyonek hesabker û hebûna makîneya Turing a ku dikare wê hesab bike vebêje.
Di warê teoriya tevliheviya hesabkirinê de, têkiliya di navbera fonksiyonek hesabker û hebûna makîneyek Turing a ku dikare wê bihejmêre girîngiyek bingehîn e. Ji bo fêmkirina vê pêwendiyê, divê em pêşî diyar bikin ka fonksiyonek hesabker çi ye û ew çawa bi makîneyên Turing re têkildar e.
Fonksiyonek hesabker, ku wekî fonksiyonek vegerî jî tê zanîn, fonksiyonek matematîkî ye ku dikare bi algorîtmayek were hesibandin. Ew fonksiyonek e ku ji bo wê makîneyek Turing heye ku, ji her têketinê re were dayîn, dê rawestîne û ji bo wê têketinê hilbera rast çêbike. Bi gotinek din, fonksiyonek hesabker ew e ku dikare ji hêla makîneya Turing ve bi bandor were hesibandin.
Makîneyên Turing, ji aliyek din ve, cîhazên hesabkirinê yên teorîk in ku ji hêla Alan Turing ve di sala 1936-an de hatine destnîşan kirin. Ew ji kasetek bêdawî ku di nav şaneyan de hatî dabeş kirin, serê xwendin/nivîsandinê ku dikare li ser kasêtê bimeşîne, û komek dewletên ku hukum dike pêk tê. tevgera makîneyê. Makîne sembolên li ser kasêtê dixwîne, li gorî rewşa xwe ya heyî û sembola ku dixwîne hin çalakiyan pêk tîne û derbasî rewşek nû dibe. Ev pêvajo heya ku makîne bigihîje rewşek rawestanê berdewam dike.
Têkiliya di navbera fonksiyonek hesabker û hebûna makîneyek Turing a ku dikare wê bihejmêre li ser bingeha têgeha Turing-temambûnê ye. Ger ku makîneyek Turing bikaribe makîneyek din a Turing simule bike tê gotin ku ew Turing-temam e. Bi gotinek din, makîneyek Turing-temam dikare her fonksiyonek ku ji hêla makîneyek din a Turing ve were hesibandin hesab bike.
Li gorî vê pênaseyê, em dikarin bibêjin ku heke fonksiyonek were hesibandin, wê hingê makîneyek Turing heye ku dikare wê bihejmêre. Berevajî vê, heke makîneyek Turing dikare fonksiyonek hesab bike, wê hingê ew fonksiyon tê hesibandin. Ev têkilî li ser vê yekê ye ku makîneyên Turing cîhazên hesabker ên gerdûnî ne ku dikarin makîneyek din a Turing simul bikin.
Ji bo ronîkirina vê pêwendiyê, em nimûneyek bifikirin. Bifikirin ku me fonksiyonek hesabker heye ku du hejmaran lê zêde dike. Em dikarin makîneyeke Turing ku du têketinan digire, serê xwendin/nivîsandinê ber bi hejmara yekem a li ser kasêtê ve digerîne, jimareya duyemîn lê zêde dike û encamê derdixe diyar bike. Ev makîneya Turing dikare fonksiyona lêzêdekirinê hesab bike, têkiliya di navbera fonksiyonek hesabker û hebûna makîneyek Turing a ku dikare wê hesab bike destnîşan bike.
Têkiliya di navbera fonksiyonek hesabker û hebûna makîneyek Turing a ku dikare wê bihejmêre li ser bingeha têgeha Turing-temambûnê ye. Fonksiyonek hesabker ew e ku dikare ji hêla makîneya Turing ve bi bandor were hesibandin, û makîneyek Turing ger ku karibe makîneyek Turingek din simule bike Turing-temam e. Ji ber vê yekê, heke fonksiyonek were hesibandin, makîneyek Turing heye ku dikare wê hesab bike, û berevajî.
Pirs û bersivên din ên vê dawiyê di derbarê Fonksiyonên kêrhatî:
- Wateya guhertoyên cihêreng ên Makîneyên Turing di kapasîteya hesabkirinê de tê çi wateyê?
- 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?