Ji°φ Peterka

St∞₧ejnφm ·kolem vÜech v∞deck²ch disciplφn, kterΘ se zab²vajφ teoretickou strßnkou poΦφtaΦ∙, je najφt dostateΦn∞ v∞rn² abstraktnφ model, na kterΘm by se daly studovat nejr∙zn∞jÜφ vlastnosti reßln∞ existujφcφch poΦφtaΦ∙, jejich aktußlnφ i potencißlnφ mo₧nosti, principißlnφ omezenφ apod., a v neposlednφ °ad∞ takΘ dokazovat r∙znß zajφmavß tvrzenφ - nap°φklad o tom, ₧e n∞co nejde spoΦφtat v∙bec, zatφmco n∞co jinΘho nejde spoΦφtat rychleji ne₧ za urΦitou dobu apod.

ZajφmavΘ je, ₧e takov²ch model∙, schopn²ch dostateΦn∞ v∞rn∞ modelovat Φinnost jak²chkoli poΦφtaΦ∙, se naÜlo vφce (nap°φklad tzv. rekurzivnφ funkce, lambda kalkulus, stroje RAM a RASP a dalÜφ). P°itom se ale p°iÜlo na velmi zajφmavou v∞c - toti₧ ₧e vÜechny tyto modely jsou navzßjem rovnocennΘ (alespo≥ v tom smyslu, ₧e ka₧d² z nich dokß₧e v∞rn∞ namodelovat vÜechny ostatnφ). V d∙sledku toho je pak mo₧nΘ vybrat si kter²koli z t∞chto vzßjemn∞ rovnocenn²ch nßstroj∙ a vystaΦit s nφm - ₧ßdn² jin² toti₧ nem∙₧e z principu odhalit n∞co, co by se s jin²m odhalit nedalo.

Modelem, kter² se mezi vÜemi vzßjemn∞ rovnocenn²mi modely stal nejvφce pou₧φvan²m, je tzv. Turing∙v stroj (Turing machine), kter² navrhl anglick² matematik Alan M. Turing v roce 1936. Turing∙v stroj je v mnoha sm∞rech podobn² koneΦnΘmu automatu, kter² jsme si popisovali minule: mß koneΦn² poΦet stav∙, ve kter²ch se m∙₧e nachßzet, postupn∞ p°ijφmß jednotlivΘ vstupy, kterΘ dostßvß ze svΘho okolφ, a reaguje na n∞ p°echodem do novΘho stavu. Na rozdφl od koneΦnΘho automatu je ale vybaven navφc jeÜt∞ i nekoneΦn∞ dlouhou pßskou, na kterou si m∙₧e zapisovat znaky z urΦitΘ pevn∞ danΘ abecedy - dφky nekoneΦnosti pßsky, kterou si Turing∙v stroj m∙₧e podle pot°eb posouvat, tak mß k dispozici nekoneΦn∞ velkou pam∞¥. Prßv∞ dφky tomu, a na rozdφl od koneΦnΘho automatu, je pak schopen namodelovat jak²koli v²poΦet, kterΘho je v principu schopen kter²koli poΦφtaΦ.

Prßv∞ vyslovenΘ tvrzenφ si ovÜem zaslou₧φ podrobn∞jÜφho vysv∞tlenφ. Dokßzat toto tvrzenφ nebude nikdy mo₧nΘ - naproti tomu d∙kaz vzßjemnΘ rovnocennosti Turingova stroje s ostatnφmi abstraktnφmi modely poΦφtaΦ∙, provΘst lze. P°φΦinou je to, ₧e jednotlivΘ modely jsou exaktn∞ definovßny, a p°φsluÜnΘ d∙kazy se tedy majφ "o co op°φt". OvÜem to, co je "v principu schopen spoΦφtat kter²koli poΦφtaΦ", je p°φliÜ vßgnφm vymezenφm, kterΘ lze interpretovat pouze intuitivn∞, ale na n∞m₧ nelze vystav∞t formßlnφ d∙kaz.

Tuto skuteΦnost si uv∞domil i sßm Alan Turing, kdy₧ v roce 1936 koncipoval sv∙j abstraktnφ model poΦφtaΦe (Turing∙v stroj). JeÜt∞ v tΘm₧e roce pak spolu s dalÜφm anglick²m matematikem, Alonzem Churchem, vyslovili domn∞nku o tom, ₧e poΦφtaΦe (s nekoneΦn∞ velkou pam∞tφ) a Turingovy stroje jsou vzßjemn∞ rovnocennΘ - tedy ₧e ke ka₧dΘmu v²poΦtu, kter² je schopen provΘst poΦφtaΦ, existuje takov² Turing∙v stroj, kter² jej provede takΘ, a opaΦn∞ ₧e ke ka₧dΘmu Turingovu stroji existuje takov² program, kter² jeho chovßnφ bude modelovat.

Domn∞nka, kterou oba matematici formulovali spoleΦn∞, je dnes znßma jako tzv. Churchova teze. Nebude mo₧nΘ ji nikdy dokßzat (kv∙li intuitivnφmu vymezenφ na stran∞ poΦφtaΦe), ale je dnes vÜeobecn∞ pova₧ovßna za platnou. Natolik, ₧e se pou₧φvß jako p°edpoklad v jin²ch formßlnφch d∙kazech - nap°φklad p°i d∙kazu, ₧e neexistuje obecn² algoritmus pro ov∞°enφ sprßvnosti libovolnΘho programu. Ale o tom zase a₧ p°φÜt∞.