Kalmár, Péter, Surányi

Kalmár, Péter, Surányi

Ők a mi filozófusaink – mondják néha matematikus berkekben a matematika alapjaival foglalkozókra, illetve a matematikai logikusokra. Valóban filozófiai lenne a munkásságuk? Néha ez csak a beszélgetésekből, az óráikon derül ki, de vannak közöttük, akiknek egy-egy szakcikkének tényleg vannak filozófiai következményei. Ha ezeket a következtetéseket nem csak életfilozófiai értelemben lehet komolyan venni, hanem akadémiai értelemben is, akkor meg is érkeztünk a matematikafilozófiai publikációk világába. Kalmár László és Péter Rózsa egészen biztosan hagyott hátra érvelő filozófiai szövegeket, de talán az is érdekes, hogy milyen téma érdekelte őket. És itt kerül a képbe a száz éve született Surányi János, akinek logikusi munkássága erősen összekapcsolódott két nagy kortársának matematikafilozófiai cikkeivel. Ebben az írásban szeretném bemutatni, hogy milyen kapcsolat van Surányi János egyik legfontosabb kutatási területének, a tágabb értelemben vett eldöntésproblémának és Kalmár László és Péter Rózsa analitikus filozófiája között.

 Kalmár, Péter, Surányi magyar matematika az analitikus filozófia határán

Surányi János születésének századik évfordulóján alkalom nyílik az utókor számára, hogy ennek a kiváló matematikusnak és az őt is magában foglaló szellemi körnek az emlékét felidézzük, és megpróbáljunk néhány fontos kérdésre válaszolni. Rögtön az elején, mint eddig szinte mindenkinek, nekem is szabadkoznom kell, hiszen a munkásságát csak két szemszögből tudom érdemben vizsgálni, az egyik a matematikai logika, a másik a matematikafilozófia. Aki csak olvas Surányiról, abban egészen biztosan felvetődik az a kérdés, hogy a három nagy egyéniség, Kalmár László, Péter Rózsa és Surányi János, világhírű logikai munkásságuk mellett vajon tekinthetők-e filozófusoknak, illetve alkotnak-e ők hárman külön matematikafilozófiai iskolát. Csábító a gondolat, hogy hetven év távlatából úgy emlékezzünk meg róluk, mint az első létező szellemi iskoláról, amely a matematika filozófiájában a „hazai” jelzőt kiérdemelheti. A kérdés azonban zavarbaejtő választ eredményez, ha megvizsgáljuk, hogy milyen nyomok árulkodnak erről az utókorra hagyott írásaikban. Máté András matematikafilozófus egy igen figyelemreméltó és sok kutatómunkáról árulkodó cikket szentelt ennek a kérdésnek, Kalmár László és Péter Rózsa – matematikusok a filozófiáról címmel, amely a Kalmárium II. kötetében jelent meg (Máté, 2008). Ezt a munkát szeretném kiegészíteni a saját meglátásaimmal, helybenhagyva az alapvető megállapításokat, ám megváltoztatva kérdéseit, és ezekre is válaszokat adva. Meglepő, hogy a kulcs éppen Surányi János személye és munkássága lesz, annak ellenére, hogy hármójuk közül ő az, akinek gyakorlatilag semmilyen írott matematikafilozófiai természetű munkájáról nem tudunk. Szerintem ők egy elfogadható értelemben matematikafilozófusok, és ha nem is alkotnak önálló iskolát, de egy elfogadható értelemben tagjai egy tágabb matematikafilozófiai iskolának, amelyet én az amerikai számításelmélész után Church-féle matematikafilozófiai iskolának neveznék, természetesen fenntartva a lehetőségét annak, hogy az érveim, amelyeket emellett felhozok, talán nem olyan nagyon erősek. Ettől függetlenül remélem, az írásom olyanok számára is sok érdekességgel szolgál, akiket nem nagyon köt le a fenti két kérdés. Akinek annyira felkeltette az érdeklődését a téma, hogy további munkák után érdeklődne, azoknak a figyelmébe ajánlom még Szabó Máté matematikatörténész páratlanul akkurátus és izgalmas észrevételeket tartalmazó két publikációját, az egyik a Kalmár’s Argument Against the Plausibility of Church’s Thesis című, a másik a Karácsony Sándor nyelvfelfogásának hatása Kalmár László korai matematikafilozófiájára című (Szabó, 2018) (Szabó, 2013).

A szereplők és a játék, amiben játszanak. A legjobb, ha az elején kezdjük, vagyis Surányi fő témájával, az eldöntésprobléma variánsaival, természetesen a sok végesmatematikai és számelméleti munkáját most nem említve. David Hilbert volt az első azok között, akik programszerűen egy olyan eszközrendszert kínáltak fel, amivel azokon a matematikai logikai kérdéseken is fogást lehetett találni, amik eddig megközelíthetetlenek voltak a matematika számára. A Hilbert-féle matematikai logikában (metamatematikában) matematikai vizsgálat tárgyává lehet tenni az olyan lényeges fogalmakat, mint maga a bizonyítás, vagy egy elmélet által leírt fogalomkörön belüli igazság, vagy ezek viszonya és sok más hasonló kérdés. Ahogy a folytonosság, a konvergencia, a közelség, vagyis az analízis fogalmai korábban képlékenyek voltak, de idővel formális megfogalmazást nyertek, úgy a bizonyítás fogalma is a matematika számára formálisan definiálhatóvá vált. És ha ez így van, azonnal felvetődik a kérdés, hogy a bizonyítás formalizációja magában hordozza-e az érvényesség kimutatásának mechnizálhatóságát: minden formálisan megfogalmazható matematikai állítás igazságértéke formálisan meghatározható-e, és ami több: igazságértéke eldönthető-e egy gépesített eljárással? Láthatóan máris filozófiai kérdéshez értünk, mégpedig ahhoz, hogy kiiktatható-e az ember a matematikai megismerésből. Két matematikakép csap itt össze. Szeretünk néha a matematikára úgy gondolni, mint egy objektív és egzakt tudományra, ami teljesen független az embertől. De ha ez így van akkor a matematikai igazság egyáltalán nem függhet az embertől és talán léteznie kellene egy olyan embermentes formális mechanizmusnak, ami legalább elvileg legyártja az állítások igazságértékét. Persze nem kell feltétlenül így lennie, de talán az első cáfolat mégsem egy másik embermentes megoldás, hanem az, hogy lehetetlen kiiktatni a matematikai igazságkeresésből magát az embert. Visszatérve Hilbertre, érdemes megnézni, ő hogyan viszonyul az eldöntéshez, mint lehetőséghez:

Arra példaként, hogy alapvető matematikai kérdéseket hogyan lehet kezelni, szeretném azt az állítást választani, hogy minden matematikai probléma megoldható. […] Egészen biztos, hogy az én bizonyításelméletem nem fog megadni egy olyan általános eljárást, amely minden matematikai problémát megoldana. Ilyen ugyanis nincs. (Hilbert, 1925, p. 384.)

A kérdés ilyen általánosan felvetése nyilvánvalóan negatív választ eredményez, ám egyáltalán nem annyira nyilvánvaló, hogy szűkebben és pontosabban értve nem kaphatunk akár pozitív választ is. Hilbert és Ackermann 1928-ban megjelent A matematikai logika alapelvei című könyvében a probléma felvetésében még az „eldöntés” szó sem szerepel csak a kérdés elnevezésében: „határozzuk meg” vagy „felismerhető-e”, hogy egy állítás a logika axiómarendszerének következménye-e vagy sem. 1928-ban ezt a problémát hívták eldöntésproblémának, németül pedig úgy: das Entscheidungsproblem (Hilbert–Ackermann, 1928/36, p. 112.). Először Gödel kísérelte meg 1931-ben pontosítani, hogy a formális-axiomatikus számelmélet (továbbiakban a Peano-aritmetika) egy állítását mikor nevezzük eldönthetőnek, éspedig az ő javaslata az volt, hogy akkor, ha – későbbi elnevezéssel, a Péter Rózsa által elkeresztelt módon – primitív rekurzív függvény számítja ki, hogy következménye-e az axiómáknak vagy sem (Gödel, 1931)(Kleene, 1981, p. 44.). Ebben az esetben ez azt jelenti, hogy az állítás negációjának a státusza is eldől ugyanezzel a számítással. Később, amikor Stephen C. Kleene (aki Gödel szóhasználatát, jelöléseit, sőt tételeinek sorszámozását is megtartotta az 1936-os cikkében) definiálta az általános rekurzív függvényt, ez a fogalom vált a problémában szereplő algoritmustól megkövetelt tulajdonsággá (Kleene, 1936). Amikor még ugyanebben az évben ebben az értelemben válaszolta meg Alonso Church a formális-axiomatikus számelmélet eldöntésproblémájára vonatkozó kérdést, már világos volt maga a kérdés is (Church, 1936a,b). Megjegyzendő, hogy ezzel nem fulladt ki a kutatás, sőt ekkor indult el igazán. Innentől kezdve az Entscheidungsproblem tágabb értelemben azt jelentette, hogy keressünk a logika nyelvében (az úgy nevezett elsőrendű nyelvekben) olyan mondathalmazokat, amelyek eldönthetőek abban az értelemben, hogy az adott halmaz esetén van olyan effektív eljárás, amely a mondatok igazságértékét véges sok lépésben kiszámítja, vagy eldönthetetlenek, mert ilyen eljárás nincs (Gurevich, 1990).

Ebbe a pezsgő matematikai logikai eszmecserébe csöppent bele Kalmár László, akinek a figyelmét a matematika megalapozásának feladataira Neumann János hívta föl. Neumann ekkor már a Hilbert-féle kutatócsoport tagja volt, és a bizonyításelmélettel kapcsolatban már több publikációval rendelkezett. Kalmár László 1928-ban saját költségen Bolognába is elment, és meghallgatta Hilbertet az ott rendezett nemzetközi matematikai kongresszuson, 1929-ben pedig egy nyarat töltött nála Göttingenben tanulmányúton (Kalmárium, 2005, Önéletrajzok). Múlhatatlan érdeklődése és állhatatos kutató munkája eredményesnek bizonyult, a harmincas években több cikke is megjelent az eldöntésprobléma egy-egy részproblémájával kapcsolatban, illetve a Gödel-tétel variánsaival is sikerrel járt. Surányi János hallgatóként Hilbertet olvasva kezdett el érdeklődni a matematikai logika iránt, és így kereste fel Kalmár Lászlót. Kalmár, a fiatal adjunktus elmondta Surányinak, hogy ez nagyon új tudományág, és tankönyvet erről nem tud neki adni, de cikkek azok bőven vannak, és ezzel meg is kezdődött szakmai kapcsolatuk, elsősorban az eldöntésprobléma témájában (Kalmárium II., 2008, Surányi-levelezés).

Kikívánkozik belőlem azonban, hogy matematikai példákkal is lefessem az eldöntésproblémát, pontosabban azt a változatát, amelyet Church tett helyre. Az első példát Kalmártól veszem, aki nagyon jól leírta, hogy miért érdekes ez a formális logikai kérdés, ami bár ártatlannak és akár megoldhatónak is látszik, ügyesen átfogalmazva már arra a sejtésre ad okot, hogy Hilbert kérdésére a válasz nemleges (Kalmár, 1957). Church egy $ (p_n)$ problémaseregről beszélt, vagyis eldöntendő matematikai problémák egy olyan sorozatáról, amelyben tetszőleges $ n$ természetes számhoz egy az $ n$-re vonatkozó állítás (vagy feladat) van rendelve. $ (p_n)$-ből csinálhatunk egy $ (chi_n)$ számelméleti függvényt, ami a 0 értéket veszi fel, ha $ p_n$ igaz (vagy megoldható) és az $ 1$ értéket, ha nem. Pl. legyen $ p_n$ az az állítás, hogy az általános $ n$-edfokú egyenletnek van általános megoldóképlete. Ekkor $ chi_n$ a $ 4$-nél nagyobb $ n$ értékekre 0, a $ 4$-nél kisebb egyenlőkre $ 1$. $ chi_n$ értékének meghatározása tehát igen egyszerű. Egy másik példa: legyen $ n>0$ egészre $ p_n$ az az állítás, hogy az $ x^n+y^n=z^n$ egyenletnek van pozitív egész megoldása. Kalmár idejében ennek a problémaseregnek a karakterisztikus függvényére nem ismertünk kiszámítási eljárást, mivel a nagy Fermat-sejtésnek nem volt még bizonyítása. Ma már a Fermat–Wiles-tétel értelmében tudjuk, hogy ennek a $ (chi_n)$ sorozata olyan, hogy ha $ n$ az $ 1$ vagy a $ 2$ szám, akkor $ chi_n=1$, ellenkező esetben pedig $ chi_n=0$. Ez tehát $ n$ függvényében elég könnyen kiszámítható. Alonso Church egy olyan $ (p_n)$ számelméleti problémasereget mutatott, amelynek $ (chi_n)$ függvénye nem kiszámítható. Ekkor van olyan $ n$ érték, amely esetén $ chi_n$ egyetlen számítógép segítségével sem számítható ki. Még elvileg sem. Church válasza felől nézve tehát a kérdés a következő: minden számelméleti $ (p_n)$ problémasereg esetén van-e olyan kiszámítási eljárás (elvi számítógép, Turing-gép, rekurzív függvény), amely az $ n$ minden értékére, mint bemenetre meghatározza a $ chi_n$ értéket. Másképpen fogalmazva van-e minden $ (p_n)$ számelméleti problémasereghez olyan paraméteres általános megoldó eljárás, amely az $ n$ paramétertől függ, és az $ n$ tetszőleges értékére a $ p_n$ probléma egy legalább számítógéppel végigkövethető $ m_n$ megoldását szolgáltatja. Ha tehát lenne a számelmélet tételeire univerzális megoldó eljárás, akkor ez a Church-féle problémasereget is megoldaná, aminek viszont nincs általános megoldó eljárása, azaz az eldöntésprobléma kérdésére a válasz ebben a felfogásban tagadó.

A számelmélet általános megoldó eljárásának megkeresése tehát, ha lenne efféle, olyan szupernehéz probléma lenne, amely minden eddig megoldhatatlan számelméleti problémánál nehezebb. Ha ugyanis meglenne, akkor egyszerűen csak ki kéne számolni a segítségével a Goldbach-sejtést, és az máris eldőlne. No, ez is az általános eldöntő eljárás létezésének nem túl intuitív voltára hívja fel a figyelmet, bár az is igaz, hogy utólag könnyű okosnak lenni.

Rekurzivitás és konstruktivitás – több mint matematika. Szeretném még felhívni a figyelmet a Gödel-tétel és az (előbbi értelemben kimondott) Church-tétel kapcsolatára, nem matematikai szempontból, inkább a matematikafilozófiai vonatkozásait kidomborítva. Ez a kapcsolat már csak azért is érdekes, mert Kalmár László és Péter Rózsa egyik közös munkája az volt, hogy a két nagy tétel ekvivalenciájára rájöttek, és a bizonyítást ki is dolgozták (Péter, 1940, p. 140). Hogy ez az eredmény nem annyira közkedvelt, az talán azért van, mert magát a Church-tételt is lehet Church gondolatmeneténél sokkal rövidebben igazolni, feltéve, hogy az a célunk, hogy belőle a Gödelt-tételt le akarjuk vezetni. Így ez a korai időkben keletkezett visszavezetés a Gödel-tételre inkább nagyteljesítményű magashegyi túrázás volt, mint a két tétel közötti kapcsolatot tisztázó, megvilágító magyarázat. Nagyon érdekes, hogy Kalmár kiváló intuíciója a Gödel-tételkörrel kapcsolatban utalásként sok helyen felbukkan. Surányival folytatott levelezéséből derül ki, hogy közvetlen kollégáival és hallgatóival (Szele Tiborral, Varga Tamással és Surányival, mint hallgatókkal ill. Péter Rózsával mint évfolyamtárssal) hosszú heteket töltöttek azzal, hogy ennek a tételkörnek a bizonyításait, majd Kalmár ehhez való hozzájárulásait megbeszéljék. Kalmár egy helyütt megemlíti, hogy Szele elégedetlen a bizonyításaival, és egyre részletesebb és részletesebb indoklásokat követel munkájuk során (Kalmárium II., 2008, Surányi-levelezés). Gödel 1931-es cikke legendásan olvasmányos és világos. Persze ő megúszta, hiszen a technikásabb, munkásabb kivitelezésű következményeket már nem dolgozta ki egy folytatólagos tanulmányban. A Kalmár-csoport ezirányú tevékenysége viszont arról árulkodik, hogy nagyon magas szintű technikai felkészültséggel és jártassággal fogtak hozzá a tételkörbeli további cikkekhez, dolgozták ki azokat és értek el velük sikereket.

Nos, nézzük ezt a kapcsolatot! Gödel első nemteljességi tétele (a Rosser-féle megfogalmazásban) azt mondja ki, hogy a Peano-aritmetika minden ellentmondásmentes, rekurzív bővítése esetén van olyan aritmetikai $ U$ mondat, amely se nem bizonyítható, se nem cáfolható az axiómák alapján. Ez az $ U$ mondat Gödelnél egy univerzális mondat, $ (forall x)A(x)$ alakú („minden $ x$ esetén $ A(x)$”), ahol $ A(x)$ olyan egyváltozós számelméleti tulajdonság, amely eldönthető abban az értelemben, hogy minden $ n$ természetes szám esetén $ A(n)$ vagy levezethető, vagy cáfolható az axiómák alapján. Gödel cikkéből kiderül, hogy $ A(x)$ primitív rekurzív, azaz minden $ n$ természetes számra egy előre meghatározható (kiszámítható) lépésszámú eljárás eldönti, hogy $ A(n)$ levezethető vagy cáfolható. Igazságértékéhez tehát nem fér kétség. A második tulajdonság, ami igaz $ A(x)$-re, hogy $ U$ pontosan akkor nem levezethető, ha minden $ n$-re $ A(n)$ igaz (azaz $ A(x)$ előző tulajdonsága miatt $ A(n)$ ilyenkor le is vezethető). Van tehát egy olyan $ (A(n))$ problémaseregünk, amelynek minden eleme levezethetően igaz, de a $ (forall x)A(x)$ állításnak már nem létezhet formális bizonyítása, mert a Gödel-tétel éppen ezt mondja ki. Elnézést kérve az Olvasótól az eddigiek miatt, végre rá tudok mutatni, hogy ezzel meg is érkeztünk a Church-tétel és a Gödel-tétel között fennálló analógiához. Ha lenne (a Peano-axiómákból kiinduló véges) bizonyítása $ U$-nak, azaz $ (forall x)A(x)$-nek, akkor ezzel egy egységes, általános bizonyítását kapnánk $ A(x)$-nek, amelyben $ x$ helyére $ n$-et helyettesítve $ A(n)$ bizonyítása adódna. Az eredmény a Church-tétel szellemében, de a Gödel-tételkörben azt mondja, hogy van olyan $ A(n)$ állítássereg, amelynek minden eleme levezethető, de nincs egy kaptafa-bizonyítás, ami ezeket az egyedi bizonyításokat egységesen legyártaná. Itt érdemes megjegyezni, hogy vannak olyan logikák, amelyek éppen az ilyen kaptafa-bizonyítások létét várják el egy bizonyítható univerzális állítástól. A finit konstruktivisták (és bizonyos intuicionista felépítések) egy $ (forall x)A(x)$ alakú állítást akkor tekintenek bizonyítottnak, ha létezik olyan $ Pi(x)$ kaptafa-bizonyítás, amelyben $ x$ helyére $ n$-et helyettesítve az $ A(n)$ állítás egy $ Pi(n)$ bizonyítását kapjuk. Érthető is egy konstruktivista nézőpontjából: a $ (forall x)A(x)$ ugyanolyan állítás mint bármelyik más, így ennek bizonyítása sem állhat végtelen sok páronként különböző ötletet tartalmazó érvelésből. Már csak ezért sem, mert egy ember csak véges sok eredeti ötletet képes elgondolni. Természetesen ennek ellenkezőjét a klasszikus logikus sem hiszi, de ő megelégszik a $ (forall x)A(x)$ olyan bizonyításával is, amiből közvetlenül, helyettesítéssel nem adódik $ A(n)$ bizonyítása, csak elhisszük, hogy van ilyen, hiszen $ (forall x)A(x)$ már be van bizonyítva.

Miután az emberiség sikeresen leküzdötte azt a pozitivista démont, hogy a bizonyításelmélészek be óhajtanák skatulyázni az emberi elmét egy számítógép belsejébe (irónia!) kiderült, hogy ezek a zavarba ejtő tudományfilozófiai kérdések nem szűnnek meg, csak átalakulnak. A hetvenes évek elején körvonalazódott, már az eldöntési eljárások világában, egy újabb matematikai sejtés és egyben matematikafilozófiai probléma. Kiderült, hogy az eldöntési problémák a kutatók kezei között nagyon gyorsan kétfélének mutatkoznak. Az egyik típusba (a $ P$-vel jelöltbe) olyanok tartoznak, amelyeknek az eldöntési algoritmusa nagyon gyorsan leáll, kicsit konkrétabban fogalmazva polinomidőben lefutnak. A másik típusba (az $ NP$-nehéznek nevezett körbe) a nagyon erős eldöntési problémák tartoznak, amelyekre az összes olyan eldöntési probléma gyorsan visszavezethető, amelynek legalább a pozitív eredményét, tehát az igenlő választ, egy alkalmas tanúval mint bemenettel, gyorsan ellenőrizni lehet. Nem tudjuk, hogy vajon minden polinomidőben ellenőrizhető probléma ($ NP$) egyben polinomidőben eldönthető-e. Ez a nevezetes $ Pne NP$ sejtés. Nagyon kevés olyan $ NP$-probléma van, ami nem bizonyult sem $ NP$-nehéznek, sem $ P$-nek. Ilyen azonban a Babai László és csoportja által eredményesen kutatott gráfizomorfizmus-probléma. Erről Rónyai Lajos olvasmányos beszámolójából tájékozódhatunk (Rónyai, 2015). És itt jön Hilbert kérdésének reinkarnációja: ha $ P=NP$ lenne, akkor az összes NP-be eső probléma eldöntési eljárásának futási ideje emberléptékűvé válna, és egyben egy ésszerű korlátozással a nemlegesen eldőlt eldöntésprobléma mégis visszaavászkodna a matematikába. Érdemes ezzel kapcsolatban felidézni Kurt Gödel levelét Neumann Jánoshoz:

Nyilvánvaló, hogy készíthetünk egy Turing-gépet, amely a predikátumkalkulus minden $ F$ formulájára és minden $ n$ természetes számra eldönti, hogy $ F$-nek van-e legfeljebb $ n$ hosszúságú bizonyítása. Legyen $ Psi(F,n)$ az a lépésszám, amire a gépnek ehhez szüksége van, és legyen $ varphi(n)=max_FPsi(F,n)$ [korlátozva az $ F$ méretét, ez az $ n$-nél rövidebb bizonyítású tételek eldöntésének időkorlátja]. A kérdés, hogy egy optimális gép esetén milyen gyorsan nő $ varphi(n)$. Megmutatható, hogy $ varphi(n)geq Kcdot n$. Ha lenne egy olyan gép, amely esetén a $ varphi(n)$ függvény $ Kcdot n$-nel nőne [lineárisan] (vagy akár $ Kcdot n^2$-nel [négyzetesen]), akkor ennek messzemenő következményi lennének. Éspedig ebből világos, hogy az következne, hogy dacára az eldöntésprobléma negatív megoldásának, eldöntendő matematikai kérdések esetén a matematikus szellemi erőfeszítései lecserélhetők lennének gépek által végzett munkára. Valóban, egyszerűen az $ n$ értékét olyan nagyra kellene választanunk, hogy ha a gép nem adna erre eredményt, akkor ok sem lenne magán a problémán tovább gondolkodni. Most, legalább is számomra úgy tűnik, hogy teljesen a lehetségesség tartományában helyezkedik el, hogy $ varphi(n)$ lassan nőjön. (Sipser, 1992)

Ami a $ P=NP$ szcenárió esetén meg is valósulna, tesszük most hozzá. Ám, ahogy az általános eldöntési eljárás létét is az intuíciónkkal ellentétesnek gondoljuk, úgy elég valószínűtlen az is, hogy ily módon valósuljon meg a matematikai igazságkeresés mechanizációja.

Töredékek eldönthetősége. Surányi János matematikai logikai tevékenysége nagyrészt arra irányult, hogy feltárja, mely formulahalmazokra vonatkozóan tudja az eldönthetőséget vagy az eldönthetetlenséget megállapítani. Kalmárral olyan elsőrendű nyelvekkel dolgoztak, amelyekben nincs egyenlőségjel, nincsenek függvényjelek (matematikai műveleti jelek) és nincsenek individuumkonstansok, csak logikai operációk (a szokásos és, vagy stb.), kvantorok (minden ($ forall$), létezik ($ exists$)), változók és relációjelek. Az már Kalmár egy korai, 1936-os, elég jelentős eredménye volt, hogy ha az elsőrendű nyelv formuláinak azon $ F$ részhalmazát tekintjük, amelyben egyetlen kétváltozós relációjelet engedünk meg (pl. $ r(x,y)$), akkor ha $ F$ eldönthető, akkor az egész elsőrendű nyelv is eldönthető, azaz az eldöntésprobléma redukálható a nyelvnek erre a töredékére. Surányi és Kalmár a későbbiekben nagyrészt ilyen esetekkel foglalkoztak. Pozitív eredményt ért el Gödel (1932), Kalmár (1933) és Schütte (1934) egymástól függetlenül az alábbi töredékre. Tekintsük azoknak a formuláknak az $ F$ halmazát (ezt úgy hívjuk, hogy az elsőrendű nyelv egy töredékét), amelyek

$displaystyle exists x_1exists x_2dotsexists x_nforall y_1forall y_2exists z_1exists z_2dotsexists z_m;varphi(x_1,dots, x_n, y_1,y_2,z_1,dots,z_m)$

alakúak, ahol $ n$ és $ m$ természetes számok, $ varphi$ pedig olyan formula, amelyben csak legfeljebb a feltüntetett változók szerepelnek és kvantorok már nem. Ilyen például a $ exists xforall y_1forall y_2;p(x,y_2)wedge(neg r(y_1))$, amennyiben $ p$ és $ r$ két, illetve egyváltozós relációjel. Az egyszerűség kedvéért az ilyen formulákat, illetve ezek osztályát a következőképpen jelöljük:

$displaystyle exists^*forall^2exists^*$

Az ilyen alakú formulákra tehát talált Kalmár eldöntési eljárást, ez tehát a tágabban értelmezett Entscheidungsproblem egy pozitív megoldása. Surányi és Kalmár eredményei, mint említettük egyetlen kétváltozós relációt felhasználó töredékekre vonatkoztak, és az általános esetre vonatkozó redukcióval mutatták meg ezekre a formulahalmazokra az eldönthetetlenséget. A tágabban értelmezett Entscheidungsproblem negatív eredményeit illetően, vagyis az eldönthetetlen töredékek területén jó ideig ők voltak a legtermékenyebb kutatópáros. Vázlatosan az eldönthetetlenségi eredményeik (Gurevich et al, 1997)

$ forall^3exists^*$ Kalmár-Surányi, 1947
$ forall^*exists$ Kalmár-Surányi, 1950
$ forall^3exists$ Surányi, 1959
$ exists^*forallexistsforall$ Surányi, 1959
$ exists^*forall^3exists$ Surányi, 1959

 

Természetesen Surányi János számos cikket publikált a véges matematika és Rényi Alfréddal együtt a valószínűségszámítás témájában is, de most csak a logikai eredményeire lehetünk tekintettel.

Ki a matematikafilozófus? Most térjünk vissza ahhoz a problémánkhoz, hogy matematikafilozófusok voltak-e a címben szereplő matematikusok, és hogy egy iskolát alkottak-e. Közülük az egyetlen, aki több matematikafilozófiai írást is hátrahagyott, Kalmár László volt. Az ő filozófiai álláspontjáról tájékozódhatunk mind Máté András, mind Szabó Máté írásaiból. Felfedezhető nála néhány jellegzetesség, ami érdekes módon sok matematikafilozófiai megközelítésbe be tud illeni. Mint ismeretes, a filozófia a jelen állás szerint két, nem feltétlenül élesen elkülönülő, módszertanában különböző ágra oszlik. Az egyik az úgy nevezett kontinentális filozófia, amely számára – az én laikus megközelítésemben – a filozófia inkább művészet vagy inkább szellemtörténeti eseménysorozat. A másik az úgynevezett analitikus filozófia, ami a matematikus folkrólból eredő megfogalmazásban „az a filozófia, amit egy matematikus is megért”. Ez utóbbinak elsődleges eszköze az érvelés, és így a diskurzus, azaz, hogy mindenki számára világos legyen mi a probléma, mi ennek a szerző által javasolt megoldása, mivel lehet érvelni emellett, és az ellenvetésekre milyen válaszok adhatók. Ebbe a diskurzusba bárki bekapcsolódhat, transzparens, hétköznapi tudományos nyelven zajlik, és érveket ütköztető a módszere. Mondanom sem kell, hogy Kalmár a második felé húzott vagy legalább is nagyon jól tetten érhetőek a filozófiai munkáiban az analitikus filozófia megközelítései, nemzetközi viszonylatban pedig kifejezetten ennek a megnyilvánulásait látjuk nála. Érdemes megjegyezni, hogy Surányi János kis intenzitással bekapcsolódott egy olyan filozófiai iskola tevékenységébe, ami kontinentálisnak tekinthető, legalább is a fenti értelemben. Ez a Dialektikus Iskola lenne, aminek a hagyományát és fellelhető szöveganyagát Surányi János fia, Surányi László, gondos odafigyeléssel ápolja. Ha például Szabó Lajosnak, az iskola oszlopos tagjának, halmazelméletről szóló írását olvassa egy matematikus, akkor nehezen állja meg nevetés nélkül, mindazonáltal kellő nyitottsággal és kontinentális eszközökkel felfegyverezve nekilátva a szövegnek, sok releváns dolog elmondható róla.

A matematikafilozófusnak a tudományszociológiában szerintem sajátos státusza van. Azt állítom, hogy mindenki, aki a matematika alapjaival foglalkozik vagy tanítja, az matematikafilozófus. Egyszerűen azért, mert ahogyan a matematika alapjait a hallgatóságnak (vagy a cikkeiben) prezentálja, árulkodik arról, hogy milyen matematikafilozófiai álláspontot képvisel. Ez más matematikai ágakban ilyen közvetlenül nem vetődik fel. Mondjuk, aki differenciálgeometriával foglalkozik, azon nem valószínű, hogy meglátszik, hogy mit gondol a matematikáról, de éppenséggel meg tud látszani, hogy mit gondol a fizika filozófiájáról, a tér szerkezetéről. Ebből a természetben föllelhető matematikafilozófusból is kétféle van. Aki nem túl tájékozott a matematikafilozófiai kérdéseikben, az a munkája során elfoglal egy álláspontot, talán nem is tudja, mely más matematikusok vagy iskolák vallják még ezt az álláspontot, vagy talán csak lexikoncikkszerű tudása van erről, de ő mindenképpen egy jól meghatározott filozófiai alapállásból tolja végig az alapok bemutatását. Ennek egy közismert velejárója, amikor az illető tollat ragad és leírja mi szerinte a matematika. Példa erre a személyes vallomásszerű, de nem feltétlenül vitaalapot adó, azaz egyirányú filozofálásra Huskell B. Curry Outlines of a formalist philosophy of mathematics c. írása (Curry, 1951). Érdekes megjegyezni, hogy Curry maga is foglalkozott elméleti számítástudománnyal, a matematika alapjairól is írt könyvet és az említett könyve címe ellenére nem formalista, hanem inkább, a 60-as években igen menő, strukturalista filozófiai alapállást vallott (Seldin, 2011). A strukturalizmus a szociálkonstruktivizmussal együtt frissítően új matematikaképek a 30-as évek unásig elemezgetett három nagy filozófiai álláspontja, a formalizmus, az intuicionizmus és a finitizmus után.

A filozófiában tájékozottabbak, vagy azok, akiknek ilyen a lelki alkata, ütköztetni is hajlandóak a véleményüket, hogy úgy fogalmazzunk a matematikafilozófiát is a matematika tudománya akadémiai módszertanának megfelelően művelik. Kalmár László és Péter Rózsa egészen biztosan ilyenek voltak. Mi több, bátran ki merem jelenteni, hogy érveik felépítését tekintve tökéletesen beleillenek a matematika analitikus filozófiájának vonulatába. Véleményem szerint ez akkor kulminált, amikor mindketten előadtak az 1957-es konstruktivitás-konferencián Amsterdamban. Ez a két előadás meg is jelent nyomtatásban (Kalmár, 1959) (Péter, 1959). Mivel Kalmár beszéde a Church-tézissel és a kizárt harmadik elvével kapcsolatos, ezért érdemes felidéznünk, hogy mit mondanak ki ezek. A Church-tézis szerint akárhogy is definiáljuk az effektív kiszámíthatóság fogalmát, azaz, hogy van egy véges eljárás, ami bemenetekhez egy kimeneti értéket ad meg, valamely (elméleti) számítógéppel való kiszámíthatóságként vagy valami ügyes programnyelvvel történő kiszámíthatóságként, szóval bármilyen módon, amire rá mernénk mondani, hogy igen, ez az a dolog, amit a véges lépésben való kiszámíthatóságtól várunk, az mindig ugyanaz lesz, mint a rekurzív kiszámíthatóság, amit Kleene definiált. A kizárt harmadik elve pedig az, hogy bár a matematikában mindig bizonyításokkal találkozhatunk, de ezek a bizonyítások az állítások igazságának a bizonyítékai, a matematikai állításokra nézve létezik egy olyan értékelés, hogy igaz-hamis, és ezt a tényt fel is használhatjuk, még ha nem tudjuk is, hogy egy még nem bizonyított állítás igaz-e vagy hamis. Például az „$ A$ vagy nem $ A$” állítás igazságához nem fér kétség, még akkor sem, ha nem tudjuk, hogy $ A$ igaz vagy hamis, mert az $ A$ és a nem $ A$ közül legalább az egyik igaz. Nos, Kalmár egy kemény diónak tekinthető érvet barkácsolt, aminek a következménye, hogy a Church-tézis és a kizárt harmadik elve egyszerre nem lehet igaz. Bár a cikkében többször is hangsúlyozza, hogy nem cáfolni akarja a Church-tézist, csak a hihetősége elleni érvet hoz fel, és hogy ugyanígy mellette is lehetne érvelni, mégis ez a mentegetőzés feltűnően gyanús akkor, amennyiben ismerjük Kalmár világos észjárását. És valóban! Mendelson négy évvel a nyomtatásban való megjelenés után rámutatott arra a tényre, hogy ha Kalmár érve helyes, akkor a Church-tézis nem pusztán implauzibilis, hanem határozottan hamis; ő maga megtalálni is vélte a rejtett premisszát, ami a konklúzióhoz vezet. Mendelson elemzése valóban elég jó alap arra, hogy ebből kiindulva talán egyszer kiderül, mi Kalmár érvével a gond (Mendelson, 1963). A Church-tézis elleni érv után a szegedi matematikus mutat is egy reménybeli eljárást, ami ugyan szerinte kiszámítási eljárás, de nem rekurzív. Ám ez az eljárás már első ránézésre sem felel meg a számításelmélészek azon intuíciójának, hogy milyennek kellene lennie egy effektív kiszámítási eljárásnak. Kleene be is számol arról, hogy ő ott volt az amsterdami konferencián, és amint hallotta Kalmár eljárását azonnal tudta, hogy nem lehet racionálisan indokolni, hogy ez az eljárás effektív eljárás lenne. Második ránézésre már gondok adódhatnak, mert Kalmár csapdát állított: minél pontosabban próbálja valaki igazolni, hogy Kalmár-eljárása nem effektív kiszámítási eljárás, annál kevésbé fog ez neki sikerülni. Érdemes megjegyezni, hogy a modern fizika diadala után már tudjuk, hogy ami egy megfigyelőnek véges időben zajlik, az egy másik megfigyelőnek akár végtelen hosszúra is nyúlhat. Talán viccesnek hangzik, pedig igaz, hogy a „véges” fogalma pont a természetet leíró törvények miatt relatív, és nem a fantáziánk csapongása miatt (bár ezeknek a törvényeknek a megtalálása meg éppen a csapongó fantázia eredménye tud lenni). Nagyon nagy tömegű forgó fekete lyukak közelében a téridő geometriája, a mi sima téridőnkhöz képest, olyannyira más, hogy fizikai szempontból nem is csak egyetlen Church-tézisről, hanem sokféle Church-tézisről beszélhetünk annak függvényében, hogy egy adott helyen az univerzum éppen milyen szerkezetű. Erre Németi István és Etesi Gábor mutatott rá egy közös cikkben (Etesi–Németi, 2002). Kalmár, nem gyenge filozófiai elköteleződéssel, azt állítja, hogy az ő kiszámítási eljárása azért effektív eljárás, mert olyan szabályszerűséget ír le, ami az objektív valóságban megtalálható; és még akkor is helyes, ha helyessége nem bizonyítható formális matematikai eszközökkel. Hogy lássuk, Kalmár nagy ellenérzést keltő kijelentése mennyire élő mégis a matematikafilozófiában, érdemes felidézni Kurt Gödel hasonló szavait egy hasonló helyzetre:

Elismerem persze, hogy minden matematikus veleszületett módon idegenkedik attól, hogy az efféle induktív érveléseknek egyfajta heurisztikus jelentőségnél többet tulajdonítson. Mégis úgy vélem, hogy ez éppenséggel abból az előítéletből fakad, mely szerint a matematikai tárgyak nem bírnak valódi egzisztenciával. Ha a matematika, a fizikához hasonlóan egy objektív világ leírása lenne, akkor nem tudnánk megindokolni, hogy miért ne alkalmazhatnánk induktív módszereket a matematikában is, éppúgy, mint a fizikában. (Gödel, 1951, p. 74.)

Péter Rózsa hasonlóképpen inkább analitikus filozófiai gondolkodású volt, bár Surányi Jánossal egyetemben ez nagyrészt abban nyilvánult meg, hogy a filozófiát gyakorlati módon alkalmazta, azaz a pedagógiában. A diskurzusra való igény nem kevés mértékére van az emberben szükség ahhoz, hogy fejest ugorjon olyan pedagógiai kísérletekbe, amilyenekben Péter Rózsa és Surányi János is részt vett, illetve amiket éppen ők kezdeményeztek. A matematika pedagógiájában éppen Surányi János kezdeményezésére fordult a kocka, és a sokszor csak előadásszerű matematikatanítási módszer helyett tantárgypedagógiai csoportja a tanulók órán való szellemi mozgósítását propagálta. Ha egy kis bátorsággal ezt a fajta pedagógiát alkalmazott analitikus filozófiának tekintjük, akkor kijelenthetjük, hogy ebben az értelemben mindhárman alkotó filozófusok voltak.

Sokféle matematikafilozófia. Az eddigiekből az is kiderült, hogy az említett nevek (Church, Kleene, Gödel, Neumann, Kalmár, Péter) nem csak matematikai problémákon dolgoztak együtt, hanem matematikafilozófiai kérdésekben is élénk vitát folytattak, nem mellesleg Hilbert, Gödel és Kalmár filozófiai problémafelvetéseinek eredményeképpen. Az olyan filozófiai irányzatok mellett, mint intuicionizmus, formalizmus, strukturalizmus sokféle megközelítésben is lehet láttatni a matematikát. Talán itt nem is a matematika egészének látképéről van szó, hanem arról, hogy milyen konkrét matematikafilozófiai kérdések foglalkoztatják a vitában résztvevőket. Vannak, akik a halmazelméleti filozófiai kérdéseket tekintik elsődleges matematikafilozófiai kérdéseknek. Mások a bizonyítás és érvelés, a logika kérdéseit. És vannak a Church köré gyűlők, akik a rekurzív kiszámíthatóságban tesznek fel filozófiai kérdéseket, és próbálnak az álláspontjaik mellett érvelni. Ebből a szempontból a jelen írásban megemlített kutatók is egy filozófiai iskolához tartoznak, ami persze nem abban az értelemben iskola, hogy a megoldási módszereiket hagyományozzák át generációról generációra, hanem, hogy hosszú ideig közös diskurzusban vesznek vagy vettek részt. A kiszámíthatóság filozófiájával foglalkozó kutatókat manapság már nyilván inkább a reinkarnálódott probléma, a $ Pne NP$ sejtés foglalkoztatja, de szép számmal akadnak, akik az igazság és bizonyíthatóság közötti kapcsolatot boncolgatják. Így az, hogy a Church-tézis vonzásterébe került kutatók és a címben szereplő nagyjaink munkája termékeny talajra hullott a filozófia területén is, az nem kérdéses.

Molnár Zoltán Gábor

BME Matematika Intézet, Algebra Tanszék

Hivatkozások

Church, A., 1936a, An unsolvable problem of elementary number theory, American Journal of Mathematics, 58, pp. 345–363.

Church, A., 1936b, A note on the Entscheidungsproblem, Journal of Symbolic Logic 1 (1):pp. 40–41.

Curry, H. B., 1951, Outlines of a Formalist Philosophy of Mathematics, Amsterdam: North-Holland Pub. Co.

Etesi, G., Németi, I., 2002, Non-Turing computations via Malament–Hogarth space-times, Int. Journ. Theor. Phys. 41, pp. 341–370.

Gödel, K., 1931, On Formally Undecidable Propositions of Principia Mathematica and Related Systems I., in From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, ed.: Jean Van Heijenoort Harvard University Press, 1967.

Gödel, K., 1951, Néhány tétel a matematika megalapozásáról és ezek következményei, in: A matematika filozófiája a 21. század küszöbén. Válogatott tanulmányok, Szerk. Csaba Ferenc, Osiris, Bp. 2003.

Gurevich, Y., 1990, On the classical decision problem. Bulletin of the EATCS, 42:140–150.

Gurevich, Y.–Börger, E.–Grädel E., 1997, The Classical Decision Problem, Springer.

Hilbert, David, 1925, On the Infinite in: From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931, ed.: Jean Van Heijenoort, Harvard University Press, 1967.

Hilbert, D.–Ackermann, W, 1928/36, Principles of mathematical logic. Chelsea Pub. Co., 1950.

Kalmár L., 1957, Az ún. megoldhatatlan matematikai problémákra vonatkozó kutatások alapjául szolgáló Church-féle hipotézisről, Az MTA Matematikai és Fizikai Osztályának Közleményei, 7.

Kalmár L., 1959, An Argument against the Plausibility of Church's Thesis, in A. Heyting (ed.), Constructivity in Mathematics. Amsterdam: North-Holland Pub. Co. pp. 72–80.

Kleene, S. C., 1936, General recursive functions of natural numbers. Mathematische Annalen 112: pp. 727–742.

Kleene, S. C., 1981, The theory of recursive functions, approaching its centennial. Bull. Amer. Math. Soc. (N.S.) 5, no. 1, 43–61.

Kalmárium, 2005, Kalmár László levelezése magyar matematikusokkal, Összeáll.: Szabó P. G., Szeged, Polygon Könyvek.

Kalmárium II., 2008, Kalmár László levelezése magyar matematikusokkal, Összeáll.: Szabó P. G., Szeged, Polygon Könyvek.

Máté András, 2008, Kalmár László és Péter Rózsa – matematikusok a filozófiáról in: Kalmárium II., Kalmár László levelezése magyar matematikusokkal, Összeáll.: Szabó P. G., Szeged, Polygon Könyvek.

Mendelson, E., On some recent criticism of Church's Thesis. Notre Dame J. Formal Logic 4, no. 3, 201–205.

Péter Rózsa, 1941, Az axiomatikus módszer korlátai, Matematikai és fizikai lapok, 48., pp. 120–143.

Péter R., 1957, Rekursivität und konstruktivität, in A. Heyting (ed.), Constructivity in Mathematics. Amsterdam: North-Holland Pub. Co. p. 226.

Rónyai L., 2015, Világraszóló magyar eredmény a számítástudományban, https://tudomany.blog.hu/2015/11/26/vilagraszolo_magyar_eredmeny_a_szamitastudomanyban, 2015. nov. 26.

Seldin, J. P., 2011, Curry's Formalism as Structuralism, Logica Universalis 5 (1): 91–100.

Sipser, M., 1992, The history and status of the P versus NP question, STOC '92 Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, ACM, New York, pp. 603–618.

Szabó Máté, 2013, Karácsony Sándor nyelvfelfogásának hatása Kalmár László korai matematikafilozófiájára, in: Nehogy érvgyülölők legyünk (Festschrift for András Máté), Chapter: Karácsony Sándor nyelvfelfogásának hatása Kalmár László korai matematikafilozófiájára, Publisher: L'Harmattan, Editors: Zsofia Zvolenszky, pp. 164–173

Szabó Máté, 2018, Kalmár’s Argument Against the Plausibility of Church’s Thesis, History and Philosophy of Logic 39 (2): pp. 140–157.