Algoritmy za hranicí vypočitatelnosti

DEFINICE Za algoritmus je standardně pokládána taková procedura, kterou dokáže realizovat Turingův stroj. Více ne...


DEFINICE
Za algoritmus je standardně pokládána taková procedura, kterou dokáže
realizovat Turingův stroj.

Více než půl století staré chápání algoritmu je možná zbytečně úzké a pro
některé účely by bylo vhodné definici rozšířit. O možných způsobech redefinice
pojmu algoritmu hovořil počítačový vědec Yuri Gurevich na konferenci Logica
2005.
Ve "standardním" pojetí, vycházejícím především z tzv. Churchovy teze, je za
algoritmus pokládána procedura, kterou dokáže realizovat Turingův stroj. Mnohým
matematikům a zejména badatelům v oboru počítačové vědy však dnes taková
definice algoritmu nevyhovuje a pro své úvahy by uvítali alternativní pojetí. I
úlohy, které nejsou na Turingově stroji řešitelné, se totiž z hlediska své
složitosti mohou lišit; rozšířená definice algoritmu by proto měla umožnit
jemnější diferenciaci i v těchto oblastech. Fakt, že nic silnějšího než
Turingův stroj nelze podle klasických představ ve fyzickém světě realizovat,
přitom není rozhodující.
Pro ilustraci snad poslouží následující příklad: Neexistuje žádný obecný
algoritmus na dělení reálných čísel, alespoň v tom smyslu, že iracionální čísla
nelze v konečném počtu kroků vyčíslit (a tudíž s nimi Turingův stroj nemůže
nijak pracovat). Pokud ale naše chápání pojmu algoritmus rozšíříme, respektive
budeme tomuto pojmu rozumět "neformálně", pak je celkem jasné, co se pod
dělením iracionálního čísla myslí. A stejně tak je jasné, že například výpočet
p/2 bude jednodušší než výpočet vztahu p na p třebaže v principu jsou obě úlohy
na Turingově stroji stejně neřešitelné. To, že dokážeme nějak definovat rozdíl
mezi oběma úlohami, má i praktický význam namísto algoritmu můžeme použít
nějakou přibližnou heuristiku (třeba p zaokrouhlíme na určitý počet desetinných
míst) a lze předpokládat, že složitost heuristik pro dělení a odmocňování bude
nějak korespondovat se složitostí příslušných "algoritmů". V tomto rozšířeném
chápání je algoritmus prostě nějaký abstraktní program zapsaný v symbolickém
jazyce, a to bez ohledu na to, zda je realizovatelný Turingovým strojem.
Yuri Gurevich, který s rozšířenou definicí algoritmu přišel, je, jak už ukazuje
jeho jméno, ruského původu. Po emigraci ze SSSR se usadil v USA a nakonec
zakotvil ve společnosti Microsoft; v Redmondu nyní působí na pozici vědeckého
pracovníka. Jeho případ mimochodem dokládá, že řada velkých firem dnes
podporuje nejenom aplikovaný, ale i základní výzkum. Gurevichův přístup také
ukazuje na vzrůstající podíl překrývání filozofické logiky (konferenci Logica
organizuje příslušná skupina Filozofického ústavu AV ČR), matematické logiky a
počítačových věd.



Slovníček

Turingův stroj: Model obecného výpočetního stroje, který je schopen číst
informaci z nekonečné pásky, posouvat se po této pásce a zapisovat na ni (jinak
řečeno na základě vstupu mění svůj stav). Výhodou Turingovy definice je, že
umožňuje chápat složitý výpočet sekvenčně jako sled určitých elementárních
operací.

Churchova teze: Jakýkoliv výpočet realizovatelný libovolným počítačem je
realizovatelný některým Turingovým strojem. Churchova teze je všeobecně
pokládána za platnou, i když její formální důkaz naráží na problém s definicemi
(co je to "jakýkoliv výpočet/počítač"?).

Heuristika: "Nestandardní" postup k řešení určité úlohy, určitá zkratka,
respektive spíše intuitivní strategie. Heuristika nemá spolehlivost algoritmu v
jeho klasickém chápání, používá se však tam, kde není spolehlivý výpočet znám,
eventuálně by byl neproveditelný (např. časově příliš náročný).









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.