Tehetséggondozás az informatikában
Bevezetés
A XX. század első felének matematikatörténetére visszatekintve két ember
munkássága bizonyosan megkerülhetetlen: Kurt Gödel és Alan Turing a
matematika évezredes épületének alapjai, illetve felépítménye kapcsán
fogalmazott meg korszakalkotó gondolatokat.
Száz évvel korábban két rövid életű, de kivételes tehetségű fiatalnak
köszönhetően megszületett már a válasz a matematika évszázadok óta
feszültséget keltő néhány kérdésére. E válaszok inkább voltak
nyugtalanítóak, mint megnyugtatóak: Niels Henrik Abel igazolta, hogy az
ötöd- és magasabb fokú egyenleteknek (a szó hagyományos értelmében) nincs
általános megoldási módszere; Évariste Galois nyomán pedig bizonyíthatóvá
vált, hogy az ókor klasszikus problémái: a kör négyszögesítése, a
kockakettőzés és a szögharmadolás feladata (ismét csak az eredeti felvetés
értelmében) hasonlóképpen megoldhatatlanok.
A fentiekhez kapcsolódó (igen nehéz, középiskolai szinten nem tárgyalható)
matematikai tételek tehát egy-egy területen megmutatták már a matematika
korlátait; Gödel viszont a matematika alapjait képező logika kutatása során
arra az általánosabb következtetésre jutott, hogy az előzőeken túl mindig
lesznek további olyan (matematikailag értelmezhető) kérdések, amelyekre a
matematika soha nem adhat választ; mi több, a matematikai axiómák esetleges
kiegészítésével sem tölthető ki az így keletkezett űr. (Pontosabban
fogalmazva az űr természetesen nem akkor keletkezett: Gödel „csak” azt
mutatta meg, hogy az ismereteink hiányára utaló fekete lyukak a a matematika
égboltján éppenhogy a matematika immanens jellemzői; a matematika alapjaiból
egyenesen következnek a matematika át nem léphető korlátai.)
Turing –nyilván a róla készült filmeknek köszönhetően is– szélesebb körben a
második világháború alatti tevékenységéről ismert: a vezetésével megépített
gépek a mai számítógépek közvetlen elődei; csoportja a német rejtjelezés
feltörésével meghatározó módon befolyásolta a háború menetét. Hasonlóan
jelentősek azonban ezt megelőző elméleti kutatásai is: olyan matematikai
modellt alkotott a később megszülető számítógépekről, amely a mai napig
érvényesnek látszik. E modell a matematika elemi objektumait használja
(halmazokat, függvényeket), s évtizedek múltával is úgy tűnik, hogy a
gyakorlatban azok és csak azok a problémák kezelhetőek, illetve oldhatóak
meg számítógéppel, amelyek a Turing-féle modell szerint is (azaz a papíron
létező Turing-géppel is) értelmezhetőek, illetve megoldhatóak.
Turing a később ténylegesen megépített számítógépek matematikai leírásával
egy időben arra is rámutatott, hogy a számítógépek soha nem lesznek képesek
bizonyos feladatok megoldására: nem létezik például olyan algoritmus, mely
bármely számítógépes program tetszőleges bemenete esetén eldönti, hogy a
program véges idő alatt megáll, avagy örökké fut-e. Ezt a kérdést megállási
probléma néven ismeri a szakirodalom, a megoldhatatlanságáról szóló tétel
bizonyítása pedig lényeges vonásaiban megegyezik Gödel egyik tételének
bizonyításával.
Lebililincselő stílusban ír e témákról is a kognitív tudományokkal
foglalkozó amerikai fizikus, Douglas Richard Hofstadter Gödel, Escher, Bach
című könyvében. E könyv magyar kiadásának 33. oldalától ismerteti a szerző
az MU-rejtvénynek nevezett feladatát…