Haltinga problēma — definīcija, neizšķiramība un Tjūringa pierādījums
Haltinga problēma — definīcija, neizšķiramība un Tjūringa pierādījums: skaidrs, dziļš ceļvedis datorzinātnē un algoritmu teorijā.
Haltinga problēma (apstāšanās problēma) datorzinātnē jautā: vai pastāv universāla programma, kura spēj ņemt jebkuru citu programmu un tās ievadi un noteikt, vai šī programma kādreiz apstāsies (terminēsies) vai darbosies mūžīgi. Citiem vārdiem, vai ir algoritms, kas "izlemj", vai dota programma ar dotu ievadi apstāsies?
Vienkārši piemēri
Piemēram, programma
while True: continue;
darbojas mūžīgi (nekad neapstājas), bet programma
while False: continue;
uzreiz apstājas. Haltinga problēma prasa vienu un to pašu atbildi tomēr visām iespējamām programmām un ievadēm.
Tjūringa pierādījuma ideja (neformāli)
Izrādās, ka nav nevienas universālas programmas P, kas spētu pareizi izlemst apstāšanos visos iespējamos gadījumos. Alans Tjūrings 1936. gadā parādīja pretrunu, pieņemot, ka tāda P pastāv, un pēc tam uzbūvējot programmu, kas noved pie neiespējamības.
Pieņemsim uz īsu brīdi, ka eksistē programma P, kura uzņemas argumentus (F, I) — kur F ir programma un I ir tās ievade — un atgriež True, ja F ar ievadi I darbosies mūžīgi, un False, ja F(I) kādreiz apstāsies. (Tas ir hipotētisks "apstāšanās spriedējs".)
def P(F, I): if F(I) runs forever: return True else: return False
No šādas programmas P mēs konstruējam programmu Q, kas pārbauda, vai programma F darbosies mūžīgi, ja tai kā ievadei nodod pašas sevi:
def Q(F): return P(F, F)
Tad definējam programmu R, kura, ņemot programmu F kā ievadi, dara sekojošo: ja Q(F) apgalvo, ka F(F) darbojas mūžīgi, tad R apstājas; ja Q(F) apgalvo pretēji, tad R sāk bezgalīgu cilpu un darbojas mūžīgi.
def R(F): if Q(F): return # terminate else: while True: continue # loop forever
Tagad raugāmies, kas notiek, ja liekam R apskatīt pats sevi, t.i., izsaucam R(R). Ir divas iespējas:
- Ja R(R) nedarbojas mūžīgi (apstājas), tad pēc R definīcijas Q(R) bija True (jo R apstājās tikai tāpēc, ka Q(R) apgalvoja, ka R(R) darbosies mūžīgi). Taču tad R(R) būtu jādarbojas mūžīgi — pretruna.
- Ja R(R) darbojas mūžīgi, tad Q(R) bija False (jo R darbību izraisīja bezgalīga cilpa tikai tāpēc, ka Q(R) sacīja, ka R(R) nedarbosies mūžīgi). Bet tad R(R) būtu jāpārtrauca — atkal pretruna.
Abos gadījumos rodas loģiska pretruna, tātad mūsu sākotnējais pieņēmums, ka eksistē universāls spriedējs P, bija nepareizs. Secinājums: universāla programma, kas izlemj apstāšanos visiem iespējamiem gadījumiem, neeksistē — haltinga problēma ir neizšķirama (undecidable).
Formālāka Tjūringa formulācija
Tjūrings formāli definēja aprēķināšanu ar Tjūringa mašīnām. Haltinga problēma tiek izteikta kā lēmumsparaugs H = { <M,w> | mašīna M apstājas, izpildot ievadi w }. Tjūrings pierādīja, ka nav nekādas Tjūringa mašīnas, kas visiem pāriem <M,w> viennozīmīgi atgrieztu "jā" tieši tad, kad M apstājas uz w, un "nē" citos gadījumos. Pierādījums izmanto līdzīgu pašatsauces/diagonalizācijas konstrukciju kā iepriekšējā neformālajā versijā.
Papildus skaidrojums un sekas
- Daļēja atpazīstamība (rekursīvi uzskaitāms): Lai gan haltinga problēma nav izlemjama, tā ir rekursīvi uzskaitāma (semidecidable): ir algoritms, kas, ņemot F un I, simulē F(I) soli pa solim; ja F(I) apstājas, simulācija to atklāj un algoritms var atzīmēt "apstājas". Ja F(I) nekad neapstājas, simulācija arī nekad nebeidzas, tātad nevar vienmēr droši pateikt "nedarbojas mūžīgi".
- Sekas praksē: No haltinga problēmas neizlemjamības izriet, ka nav universālas metodes, kas garantēti spēj izmantot programmatūras statisku analīzi, lai visos gadījumos noteiktu, vai programma satur bezgalīgas cilpas vai beigsies. Tomēr prakses rīki (analizatori, model checkeri, formālie pierādījumi) var un tiek izmantoti ierobežotos vai speciālos gadījumos, kur problēma kļūst izlemjama vai var aproksimēt atbildi.
- Sae saistītie rezultāti: Haltinga problēmas neizlemjamība ir plaši izmantojama, lai pierādītu neizlemjamību citiem uzdevumiem (izmantojot reducēšanu). Tāpat Rice teorēma nodrošina vispārīgākus rezultātus par to, ka visas nemantoto programmu īpašību pārbaudes ir neizlemjamas, ja tām nav banāla rakstura.
Vēsturiskā piezīme
Šo fundamentālo rezultātu 1936. gadā demonstrēja Alans Tjūrings. Tjūringa darbs izveidoja pamatus teorētiskajai datorzinātnei un mūsu izpratnei par to, kas ir aprēķināms.
Īss kopsavilkums
- Haltinga problēma: jautājums, vai pastāv algoritms, kas visos gadījumos var pateikt, vai dota programma ar dotu ievadi apstāsies.
- Rezultāts: nav universāla algoritma — problēma ir neizšķiramā (undecidable).
- Bet: haltinga problēma ir semidecidable — var apstiprināt gadījumus, kad programma apstājas, bet nevar visos gadījumos pierādīt, ka tā nekad neapstāsies.
Jautājumi un atbildes
J: Kas ir Halting problēma?
A: Haltinga problēma ir problēma datorzinātnē, kas aplūko datorprogrammu un nosaka, vai programma darbosies mūžīgi vai nē.
J: Kā mēs varam zināt, vai programma atrisina apstāšanās problēmu?
A: Mēs sakām, ka programma "atrisina apstāšanās problēmu", ja tā var apskatīt jebkuru citu programmu un noteikt, vai šī programma darbosies mūžīgi vai nē.
J: Vai ir veids, kā pierādīt, ka šādas programmas nav?
A: Jā, parādot, ka, ja tāda programma pastāvētu, tad notiktu kaut kas neiespējams. Šo pierādījumu 1936. gadā atrada Alans Tjūrings.
J: Ko dara P?
A: P ir funkcija, kas izvērtē citu funkciju F (izsaukta ar argumentu I) un atgriež true, ja tā darbojas mūžīgi, un false, ja tā darbojas mūžīgi, un false, ja tā darbojas mūžīgi.
J: Ko dara Q?
A: Q aplūko citu programmu un pēc tam atbild uz jautājumu, vai šīs pašas programmas palaišana pašai uz sevi radīs vai neradīs bezgalīgu cilpu. Tas to dara, izmantojot P, lai veiktu dotās funkcijas F novērtēšanu.
J: Ko dara R?
A: R aplūko citu programmu un lūdz Q atbildi uz šo jautājumu par šo konkrēto programmu. Ja Q atbild "jā, ja mēs palaidīsim šo programmu un liksim tai apskatīt pašas programmas kopiju, tā darbosies mūžīgi", tad R apstājas; taču, ja Q atbild "nē, ja mēs palaidīsim šo programmu un liksim tai apskatīt pašas programmas kopiju, tā nestrādās mūžīgi", tad R ieiet bezgalīgā cilpā un darbojas mūžīgi.
Jautājums: Kas notiek, ja liekat R skatīties uz sevi?
A: Var notikt divas lietas - vai nu R apstāsies, vai arī darbosies mūžīgi, bet abi rezultāti ir neiespējami saskaņā ar to, kas ir pierādīts par to, ka tādas programmas kā P neeksistē, tāpēc kaut kur pa ceļam, kas noveda pie tā, ka R skatījās uz sevi, kaut kas ir noticis nepareizi.
Meklēt