Student World

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 např. 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 výpočet Pí/2 bude jednodušší než výpočet odmocniny z 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 Logika organizuje příslušná skupina Filozofického ústavu AV ČR), matematické logiky i počítačových věd.

Na konferenci Logica 2005 zazněla i celá řada dalších zajímavých příspěvků. Několik prezentací bylo věnováno problému lháře (zhruba řečeno problému, jak se v logice a sémantice vypořádat s větami typu "já právě teď říkám nepravdu"). S tímto problémem souvisela přednáška Grahama Priesta z University Melbourne. Priest hájil přístup tzv. parakonzistentní logiky, tj. logického systému, který umožňuje pracovat i se spory-kontradikcemi, tedy větami nabývající obou pravdivostních hodnot. V klasické logice je výskyt kontradikcí nepřijatelný – jakmile totiž připustíme výskyt kontradikce, můžeme už v systému dokázat cokoliv, jakýkoliv výrok i jeho negaci. Systém se tak stává nepoužitelným. Priest, který je klíčovou postavou školy parakonzistentní logiky, se však snaží dokázat, že chápání kontradikce v klasické logice je zbytečně přísné. Pokud například dojde v přírodních vědách k nějakému sporu, ještě to neznamená znehodnocení výsledků mimo "postiženou oblast". Ze sporu nemusí být nutně odvoditelné cokoliv. Proponenti parakonzistentní logiky usilují o to, aby se oblast kolem kontradikce dala nějakým rozumným způsobem "zapouzdřit".

autor Pavel Houser