Pirsgirêka rawestandina makîneyek Turing biryardar e?
Pirsa ka gelo pirsgirêka rawestandina makîneyek Turing dikare were çareser kirin mijarek bingehîn e di warê zanistiya komputerê ya teorîkî de, nemaze di warên teoriya tevliheviya hesabkerî û biryarbûnê de. Pirsgirêka sekinandinê pirsgirêkek biryarê ye ku dikare bi awayekî nefermî wiha were diyar kirin: danasîna makîneyek Turing û têketinek tê dayîn, diyar bikin ka makîneya Turing dê di dawiyê de bisekine dema ku bi wê têketinê re were xebitandin, an gelo ew ê herheyî bixebite.
Ji bo çareserkirina çareseriya pirsgirêka rawestanê, pêdivî ye ku meriv têgeha biryarbûnê bixwe fam bike. Ger algorîtmayek hebe ku bikaribe ji bo her mînakek pirsgirêkê di demek bêdawî de bersivek erê-an-na rast peyda bike pirsgirêkek biryardar e. Berevajî vê, heke algorîtmayek wusa tune be, pirsgirêk nayê çareser kirin.
Pirsgirêka rawestandinê yekem car ji hêla Alan Turing ve di sala 1936-an de hate destnîşan kirin û îspat kir ku ew neçar e. Belgeya Turing mînakek klasîk a argumanek diagonalîzekirinê ye û tê de karanîna biaqilane ya xwe-referans û nakokiyê vedihewîne. Delîl dikare bi vî rengî were destnîşan kirin:
1. Texmîna Decidability: Bihesibînin, ji bo xatirê nakokî, ku makîneyek Turing (H) heye ku dikare pirsgirêka rawestandinê biryar bide. Ango, (H) cotek ((M, w)) wekî têketinê digire, li wir (M) ravekirina makîneya Turingê ye û (w) xêzek têketinê ye û (H(M, w)) vedigere " erê" heke (M) li ser (w) raweste û "na" heke (M) li ser (w) nesekine.
2. Çêkirina Makîneyeke Paradoksî: Bi karanîna (H), makîneyek Turing (D) ya nû ava bike ku yek têketinek (M) digire (ravekirina makîneyek Turing) û wiha tevdigere:
– ( D(M) ) direve ( H(M, M) ).
– Ger ( H(M, M) ) vegere "na", wê demê (D(M) ) disekine.
– Heke ( H(M, M) ) "erê" vegerîne, wê gavê (D(M) ) bikeve xelekeke bêdawî.
3. Xweserî û Nakokî: Dema ku (D) raveka xwe wekî têketinê tê dayîn, reftarê bihesibîne. Bila (d) bibe wesfê (D). Wê demê du dozên me hene:
- Ger (D(d)) raweste, wê demê li gorî pênaseya (D), (H(d, d)) divê "na" vegere, ku tê vê wateyê ku (D(d)) nabe ku raweste - nakokî.
- Ger (D(d)) raweste, wê demê li gorî pênaseya (D), (H(d, d)) divê vegere "erê", ku tê vê wateyê ku (D(d)) divê raweste - dîsa, nakokî. .
Ji ber ku her du halet ber bi nakokîyekê ve diçin, divê texmîna destpêkê ya ku (H) heye xelet be. Ji ber vê yekê, pirsgirêka rawestandinê nayê çareser kirin.
Ev delîl destnîşan dike ku algorîtmayek gelemperî tune ku bikaribe pirsgirêka sekinandinê ji bo hemî makîneyên Turing û têketinên gengaz çareser bike. Neçareseriya pirsgirêka rawestandinê ji bo sînorên hesabkirinê û ya ku dikare bi algorîtmîkî were destnîşankirin bandorek kûr heye. Ew destnîşan dike ku sînorên xwerû yên ku meriv dikare were hesibandin hene, û hin pirsgirêk li derveyî her algorîtmayê ne.
Ji bo bêtir ronîkirina encamên pirsgirêka rawestandinê, mînakên jêrîn bifikirin:
- Verification Program: Dibe ku meriv bixwaze verast bike ku bernameyek diyarkirî ji bo hemî têketinên gengaz bi dawî dibe. Ji ber neçarbûna pirsgirêka sekinandinê, ne mimkûn e ku meriv verastkerek bername-armanca gelemperî biafirîne ku dikare ji bo her bername û têketina gengaz diyar bike ka dê bername raweste.
- Analyzeriya Ewlekariyê: Di ewlehiya sîber de, dibe ku meriv bixwaze analîz bike ka perçeyek malware dê di dawiyê de cîbicîkirina rawestîne. Neçareseriya pirsgirêka rawestandinê tê vê wateyê ku algorîtmayek gelemperî tune ku dikare diyar bike ka dê malwareyek hatî dayîn raweste an na.
- Delîlên Matematîkî: Pirsgirêka rawestandinê bi teoremên netemambûnê yên Gödel ve girêdayî ye, ku diyar dikin ku di her pergalên fermî yên têra xwe bihêz de, gotinên rast hene ku di hundurê pergalê de nayên îsbat kirin. Neçareserbûna pirsgirêka rawestanê nîşan dide ku di derheqê tevgera algorîtmayan de pirs hene ku di çarçoweya hesabkirina algorîtmîkî de nayên bersivandin.
Neçareserbûna pirsgirêka rawestandinê jî dibe sedema têgîna kêmbûnî di teoriya tevliheviya hesabkirinê de. Pirsgirêka (A) tê gotin ku ji bo pirsgirêkek (B) dikare were kêmkirin heke çareseriya (B) ji bo çareserkirina (A) were bikar anîn. Ger pirsgirêka rawestandinê çareserî bûya, wê hingê gelek pirsgirêkên din ên neçareserkirî jî dikarin bi kêmkirina pirsgirêka rawestandinê werin çareser kirin. Lêbelê, ji ber ku pirsgirêka rawestandinê neçar e, her pirsgirêkek ku dikare ji bo pirsgirêka sekinandinê were kêm kirin jî neçar e.
Pirsgirêka rawestandina makîneyek Turing neçar e. Ev encam bingehek ji zanistiya komputerê ya teorîkî ye û ji bo têgihiştina me ya hesabkirinê, sînorên algorîtmîkî, û cewhera rastiya matematîkî, encamên dûrûdirêj heye.
Pirs û bersivên din ên vê dawiyê di derbarê Biryardarî:
- 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)?
- Wateya guhertoyên cihêreng ên Makîneyên Turing di kapasîteya hesabkirinê de tê çi wateyê?
- Ma zimanek naskirî dikare binekomek zimanê biryardar pêk bîne?
- Ger du TM-yên me hene ku zimanek biryardar diyar dikin, gelo pirsa wekheviyê hîn jî nayê biryar?
- Pirsgirêka pejirandinê ji bo otomatên xêzkirî ji ya makîneyên Turing çawa cûda dibe?
- Mînakek pirsgirêkek bide ku dikare ji hêla otomatek sînorkirî ya xêz ve were biryardan.
- Di çarçoweya otomatên sînorkirî yên rêzê de têgeha biryardarbûnê rave bikin.
- Mezinahiya kasêtê di otomatên xêzkirî de çawa bandorê li hejmara veavakirinên cihê dike?
- Cûdahiya sereke di navbera otomatên sînorkirî yên rêzkirî û makîneyên Turing de çi ye?
- Pêvajoya veguhertina makîneyek Turing li komek çîpên ji bo PCP-ê vebêjin, û ka van pêlikan çawa dîroka hesabkirinê temsîl dikin.
Pir pirs û bersivan di Decidability de bibînin