Apstāšanās problēma
Haltinga problēma ir problēma datorzinātnē. Šī problēma ir aplūkot datorprogrammu un noskaidrot, vai programma darbosies mūžīgi vai nē. 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ē.
Piemēram, šāda programma:
while True: turpināt;cilpa būs mūžīga, bet programma
while False: turpināt;ļoti ātri apstājas.
Vai ir programma, kas atrisina apstāšanās problēmu? Izrādās, ka tāda nav. Mēs pierādām šo faktu, parādot, ka, ja ir programma, kas atrisina apstāšanās problēmu, tad notiek kaut kas neiespējams. Tāpēc pagaidām rīkosimies tā, it kā patiešām būtu programma, kas atrisina apstāšanās problēmu. Šeit P ir funkcija, kas izvērtē funkciju F (izsaukta ar argumentu I) un atdod true, ja tā darbojas mūžīgi, un false pretējā gadījumā.
def P(F, I): if F(I) darbojas mūžīgi: return True; else: return False;P var apskatīt jebkuru programmu un noskaidrot, vai tā darbosies mūžīgi vai nē. Mēs izmantojam P, lai izveidotu jaunu programmu, ko sauksim Q. Q aplūko citu programmu un pēc tam atbild uz šādu jautājumu: "Ja mēs palaidīsim šo programmu un liksim tai apskatīt savu kopiju, vai tā darbosies mūžīgi?". Mēs varam izveidot Q, jo mums ir P. Viss, kas mums jādara, ir jāpasaka Q, lai izveido jaunu programmu, kas ir vecā programma, kura skatās pati uz sevi, un pēc tam jāizmanto P, lai noskaidrotu, vai jaunā programma darbojas mūžīgi vai ne.
def Q(F): return P(F, F);Tagad mēs izveidojam citu programmu R. R skatās uz citu programmu un jautā Q, lai uz to atbildētu. Ja Q atbild: "jā, ja mēs palaidīsim šo programmu un liksim tai skatīties uz savu kopiju, tā darbosies mūžīgi", tad R apstāsies. 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.
def R(F): if Q(F): return; //terminate else: while True: continue; //loop foreverTagad aplūkosim, kas notiks, ja liksim R apskatīt savu kopiju. Var notikt divas lietas: R apstāsies vai darbosies mūžīgi.
Ja, palaižot R un liekot tai apskatīt savu kopiju, tā nedarbosies mūžīgi, tad Q atbildēja: "jā, ja mēs palaidīsim šo programmu un liksim tai apskatīt savu kopiju, tā darbosies mūžīgi". Bet Q to teica, skatoties uz pašu R. Tātad Q patiesībā teica: "jā, ja palaidīsim R un liksim tai skatīties uz sevis kopiju, tā darbosies mūžīgi". Tātad: Ja R, kas darbojas uz savas kopijas, nedarbojas mūžīgi, tad tas darbojas mūžīgi. Tas nav iespējams.
Ja, palaižot R un liekot tai apskatīt savu kopiju, tā darbojas mūžīgi, tad Q atbildēja: "nē, ja mēs palaidīsim šo programmu un liksim tai apskatīt savu kopiju, tā nestrādās mūžīgi". Bet Q to teica, skatoties uz pašu R. Tātad Q patiesībā teica: "nē, ja mēs palaidīsim R un liksim tai skatīties uz sevis kopiju, tā nedarbosies mūžīgi". Tātad: Ja R, kas darbojas uz savas kopijas, darbojas mūžīgi, tad tas nedarbojas mūžīgi. Tas arī nav iespējams.
Lai kas notiktu, mēs nonākam neiespējamā situācijā. Mēs kaut ko darījām nepareizi, un mums ir jānoskaidro, kas tas bija. Lielākā daļa no lietām, ko mēs darījām, nebija nepareizas. Mēs nevaram apgalvot, ka "likt programmai skatīties uz savu kopiju ir nepareizi" vai "skatīties, ko teica cita programma, un pēc tam ieiet cilpā, ja tā teica vienu lietu, un apstāties, ja tā teica citu lietu", ir nepareizi. Nav jēgas teikt, ka mums nav atļauts darīt šādas lietas. Vienīgā lieta, ko mēs darījām un kas izskatās, ka varētu būt nepareiza, ir tā, ka mēs izlikāmies, ka tāda programma kā P vispār pastāv. Un tā kā tā ir vienīgā lieta, kas varētu būt nepareiza, un kaut kam ir jābūt nepareizam, tad tā ir nepareiza. Tas ir pierādījums, ka tāda programma kā P neeksistē. Nav tādas programmas, kas atrisinātu apstāšanās problēmu.
Šo pierādījumu 1936. gadā atrada Alans Tjūrings.
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.
