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 teoremayeke fermî ye ku were îsbatkirin; lê belê, ew hîpotezek li ser xwezayê ye
- Weşandin Pîroz, EITC/IS/CCTF Bingehên Teoriya Tevliheviya Hesabkirinê, Recursion, Makîna Turing ku danasînek li ser xwe dinivîse
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?
Pirsa ka çînên P û NP wekhev in yek ji wan pirsgirêkên vekirî yên herî girîng û dirêj-mayînde ye di warê teoriya tevliheviya hesabkirinê de. Ji bo çareserkirina vê pirsê, pêdivî ye ku meriv pênasîn û taybetmendiyên van çînan, û hem jî encamên dîtina çareseriyek bikêr-polnomial-demê fam bike.
Ma makîneyek turing dikare zimanek biryar bide û nas bike û fonksiyonek jî hesab bike?
Makîneya Turing (TM) modelek hesabkerî ya teorîkî ye ku di teoriya hesabkirinê de rolek navendî dilîze û bingehek ji bo têgihîştina sînorên tiştê ku dikare were hesibandin pêk tîne. Navê matematîkzan û mantiqnasê Brîtanî Alan Turing, makîneya Turing amûrek razber e ku sembolên li ser xêzek manîpule dike.
Ma pola NP dikare bi çîna EXPTIME re wekhev be?
Pirsa ka gelo çîna NP dikare bi pola EXPTIME re wekhev be, di aliyên bingehîn ên teoriya tevliheviya hesabkerî de vedigere. Ji bo çareserkirina vê pirsê bi berfirehî, pêdivî ye ku meriv pênasîn û taybetmendiyên van çînên tevliheviyê, têkiliyên di navbera wan de û encamên wekheviyek wusa fam bike. Pênase û Taybetmendî
Ma kasetek dikare bi mezinahiya têketinê ve were sînordar kirin (ku wekhev e ku serê makîneya turingê bi sînorkirî ye ku ji têketina kasêta TM-yê wêdetir bimeşe)?
Pirsa ka kasetek dikare bi mezinahiya têketinê ve were sînordar kirin, ya ku bi serê makîneyek Turing re sînordar e ku ji ketina li ser kasêtê wêdetir derbas bibe, dikeve nav qada modelên hesabkerî û astengiyên wan. Bi taybetî, ev pirs li ser têgehên Linear Bounded disekine
Ma hemî zimanên Turing têne naskirin?
Pirsa ku hemî ziman bi Turing têne naskirin, pirsek bingehîn e di warê teoriya tevliheviya hesabkirinê û teoriya hesabkirinê de. Ji bo bersiva vê pirsê bi berfirehî, girîng e ku meriv pênasîn û taybetmendiyên makîneyên Turing, çînên zimanên ku ew nas dikin, û cûdahiyên di navbera celebên cûda de binirxînin.
Ma P û NP bi rastî heman çîna tevliheviyê ne?
Pirsa ku P bi NP re ye yek ji pirsgirêkên herî kûr û neçareserkirî ye di zanistiya kompîturê û matematîkê de. Ev pirsgirêk di dilê teoriya tevliheviya hesabkirinê de ye, qadek ku dijwariya xwerû ya pirsgirêkên hesabkeriyê lêkolîn dike û wan li gorî çavkaniyên ku ji bo çareserkirina wan hewce ne dabeş dike. Ji bo fêmkirina
Di teoriya tevliheviya hesabkerî de girîngiya teorema vegerandinê çi ye?
Teorema vegerê di teoriya tevliheviya hesabkerî de, nemaze di warê ewlehiya sîber de, girîngiyek girîng digire. Ev teorem çarçoveyek bingehîn ji bo têgihîştina tevger û sînorên fonksiyonên paşverû, yên ku di gelek kar û algorîtmayên hesabkirinê de bingehîn in, peyda dike. Di bingeha xwe de, teorema vegerandinê diyar dike ku her fonksiyonek hesabker dikare ji hêla ve were hesibandin
Teorema vegerê çawa rê dide afirandina makîneyek Turing a ku dikare li gorî şiroveya xwe bixebite?
Teorema vegerê têgehek bingehîn e di teoriya tevliheviya hesabkirinê de ku destûrê dide afirandina makîneyek Turing ku karibe li ser danasîna xwe bixebite. Ev teorem ji bo têgihîştina sînor û kapasîteyên hesabkirinê amûrek hêzdar peyda dike. Ji bo ku fêm bikin ka teorema vegerê çawa diafirîne makîneyek Turing a wusa,
Çend mînakên operasyonên ku dikarin li ser makîneya Turing bêne kirin çi ne?
Makîneya Turing modelek hesabkerî ya teorîkî ye ku ji kasetek bêdawî ku li hucreyan hatî dabeş kirin, serê xwendin-nivîsandinê, û yekîneyek kontrolê pêk tê. Yekîneya kontrolê ji bo destnîşankirina tevgera makîneyê berpirsiyar e, ku tê de pêkanîna operasyonên cihêreng li ser kasêtê ye. Van operasyonan ji bo pêkanîna hesaban û çareserkirina pirsgirêkan girîng in.