Incompetent fuckwits

Seriously.

I've read someone on Reddit, commenting on the original article:

To me at least, the equations are extremely intimidating - all the greek letters and symbols and so on.

Intimidating. Intimidating. What the fuck?! But the best one's got to be this gem:

I am aware these are not especially difficult formulas, as far as math goes... and in a long forgotten past I probably learned how to read them. Still, they're too obfuscated for my tastes.

How can you forget stuff like the meaning of Σ or Π as accumulators? It's not some esoteric notation you use once in some obscure college course and never again. This is what you use, in a CS course, every damn day, at least while you're still in college.

I'm not one to rant about random shit like that. Ignorant people are everywhere. But to be so proud of it — this is truly baffling.

Iskola az őrület határán

Vajon mi lehet az oka, hogy az iskolában a gyerekeket osztályokba sorolják?

Avagy másképpen, milyen lehetett az az iskola, ahol először halmazokba próbálták rendezni a lurkókat, de Rekurzív Pistike és osztálytársai Rekurzív Pistike annyi gondot okoztak, amikor a tanárok (köztük főleg az osztályfőnök, egy bizonyos Russell tanár úr) meg akarták állapítani, hogy ki hiányzik az óráról, hogy kénytelenek voltak inkább csak osztályokba rakni a gyerekeket...

Sapkakiválasztási axióma

Az egész egy ártatlannak tűnő fejtörővel kezdődött, amit András hozott a brigádnak. A feladat így szól:

Egy börtönben megszámlálhatóan végtelen rab raboskodik. Az unatkozó börtönőrök azt találják ki, hogy mindegyik rab fejére piros vagy kék sapkát húznak, úgy, hogy senki se lássa, a saját fejére milyen színű kerül, majd miután a rabok jól megnézték egymást (minden rab a sajátján kívül az összes többi rab sapkáját látja), mindegyiküktől megkérdezik, milyen színű sapka van a fején. Ha legfeljebb véges számosságú rossz válasz születik, a rabokat mind elengedik. Milyen stratégiát találjanak ki a rabok, hogy biztosan kijussanak?

Sajnos szerdán közölte a feladatot, és én először csütörtökön voltam dolgozni, úgyhogy addigra Encsének már volt egy (tudottan rossz) megoldás-vázlata. A következőek miatt fontos megismernünk ezt a megoldást, és azt is, hogy miért rossz.

Tegyük fel, hogy a rabok előre sorba rendeződnek, és megállapodnak egy algoritmusban, ami megszámlálhatóan végtelen hosszú piros/kék sorozatokat állít elő. Amikor minden rab fején sapka van már, mindegyik rab elkezdi futtatni az algoritmust, és megnézik, vajon az első, második, ... sorozatra igaz-e, hogy legfeljebb véges esetben adna hibás választ, ha az n. rab válasza az aktuális sorozat n. tagja lenne. A saját sapkájukat nem ismerve is mindannyian ugyanara a sorozatra fogják először megállapítani, hogy megfelelő. Ezekután valamennyi rab e szerint a sorozat szerint fogja a ráeső sapka-színt válaszolni.

Ha az őrök ki tudják kérdezni a rabokat, és meg is tudják állapítani, hogy legfeljebb véges rossz válasz született, akkor ezeket a műveleteket megengedettnek vehetjük (használhatjuk a börtönőrök algoritmusait), vagyis a végtelen sorozatok előállítását és egyes sorozatok ellenőrzését elvégezhetik a rabok.

A megoldás mégsem helyes, mivel könnyen látható (közvetlenül Cantor módszerével, vagy pl. a sapka-sorozatokat kettedesjegy-bitsorozatként értelmezve, a [0,1]-beli valós számokkal azonosítva), hogy a lehetséges sapkasorozatok kontinuum számosságúak, ezért nem sorolhatóak fel, vagyis egy mégoly erős algoritmus, amelyet a feladat, mint láttuk, implicit megenged, és könnyedén előállít végtelen bitsorozatokat, sem tudná valamennyi lehetséges sorozatot előállítani.

De vajon szükség van-e valamennyi sorozat előállítására? Nyilván nem, hiszen sok olyan sorozat van, amelyek közül egy adott sapka-leosztás esetén bármelyikre is jutnak a rabok az algoritmust futtava, a rossz válaszok száma legfeljebb véges. Definiáljunk ugyanis egy olyan binér relációt a megszámlálhatóan végtelen hosszú bitsorozatok felett, amelyben két sorozat relációban van, ha van olyan index, amelytől megegyeznek, vagyis legfeljebb véges tagjuk tér el. Ez a reláció nyilván ekvivalencia-reláció, és a raboknak elegendő egy olyan algoritmus, amely minden ekvivalencia-osztályból előbb-utóbb előállít legalább egy sorozatot.

Mármost vizsgáljuk meg az ekvivalencia-osztályok számát! Sajnos azt kapjuk, hogy ezek továbbra sem megszámlálhatóak, hiszen egy-egy osztálya úgy áll elő, hogy vesszük egy reprezentánsát, majd hozzávesszük azokat az egyéb sorozatokat, amelyek tőle egy tagban térnek el (ilyenből nyilván megszámlálhatóan végtelen van), amelyek két tagban (szintén), és így tovább. Megszámlálhatóan végtelen darab megszámlálhatóan végtelen halmaz uniója azonban még mindig csak megszámlálhatóan végtelen. Mivel az osztályok uniója, vagyis az összes sorozat megszámlálhatatlan, nyilván az osztályok száma is az.

A fenti gondolatmenet alapján tehát bárki meggyőzhető, hogy az ismeretett megoldás hibás. Csakhogy András egy ehhez nagyon hasonló megoldást ismertetett kanonizáltként (mint kiderült, a feladatot, és a megoldását ő matek-szakos hallgatóktól hallotta): a rabok megállapodnak ekvivalenciaosztályonként egy-egy reprezentánsban, és amikor az őrök kikérdezik őket, mindannyian a látott sapkák által meghatározott osztály reprezentánsának tagjaival válaszolnak.

Persze amikor ezt András előadta, kitört a pokol, mert átverve éreztük magunkat. Ugyan hogyan tudnának megállapodni a rabok az ehhez szükséges ℝ→ℝ függvényben, ha általában még a valós számok egy részhalmazára sem adható kiszámítható szelektorfüggvény? Mint kiderült, a forrásnak számító matekhallgatókat ez a részlet egyáltalán nem zavarta.

Aztán rákerestünk a neten, és kiderült, amit már akkor éreztem a zsigereimben, amikor a "megoldást" hallottuk: a megoldás valójában a kiválasztási axiómán függ, nem is lehetne konstruktív. Persze a linkelt oldallal ellentétben én nem gondolom, hogy ebből a kiválasztási axióma valamiféle értékelését vonhatjuk le, viszont szerintem az eredeti feladatban szereplő rabokon fikarcnyit sem segít bármilyen, nem-konstruktív módszer.

És innentől válik a kérdés filozófiaivá, és itt dobom be a gyeplőt a leendő kommentelők közé: szerintetek mi a helyzet?

Folytatásos könyvek a bábeli könyvtárban

A minap újraolvastam Borges Bábeli könyvtárát, és egy pillanatra meglódult az agyam. Az alábbi gondolatmenetet főleg a nem progmatos olvasóimnak szánom. A progmatosoknak ez spanyolviasz :)

Az jutott ugyanis eszembe, hogy mi van a 410 oldalnál hosszabb könyvekkel, ezek talán hiányzonának a Teljes Könyvtárból? Természetesen nem, hiszen folytatásos kiadásuk könnyen szerepelhet a kínálatban. Így viszont látszólagos ellentmondásra jutunk: a Könyvtár nyilvánvalóan véges számosságú könyve ezek szerint a megszámlálhatóan végtelen számosságú összes könyvet tartalmazná, mindegyiket véges számú folytatásokra osztva?

Az ellentmondás feloldását az adja, ha megvizsgáljuk, mi a helyzet az egy sorozatba tartozó kötetek sorrendjével, mint információval. Tegyük fel például, hogy minden kötet így kezdődik:

Kellően hosszú könyv esetén azonban (és mivel az összes könyvet tárolni akarjuk, lesz közte ilyen hosszú könyv is) a sorszám leírása önmagában kitölti mind a 410 oldalt. Bármilyen kódolást is használunk a sorszám leírására, mivel egy könyvben kb. 410∙80∙40 betű van, ha azt akarjuk, hogy a sorszám után még egy tartalmi betű is elférjen, az első kötettől legfeljebb a 25^{410∙80∙40-1}+1. kötetig sorszámozhatjuk folyamatosan a könyveket. És akkor ebben még nem is hagytunk helyet a sorozat azonosításának.

És ha a sorrendet valahogyan "kívül" tároljuk?

Akkor pont nem állítunk semmit. Ez rögtön látszik, ha rövidebb, mondjuk egyetlen, 0 és a 9 közötti számjegyet tartalmazó könyvekről beszélünk. Ekkor tíz "könyvünk" van, mégis bármilyen nagy természetes szám tizes számrendszerbeli reprezentációja előáll mint "folytatásos regény". Csakhogy ekkor a könyvek gyakorlatilag semmilyen információt nem hordoznak egyetlen számról sem, az információ ugyanis a könyvek sorrendjében van. Az pedig a Könyvtár rendszerén kívül.

Merre megy a matematika?

Mint progmatos, apám felé én vagyok a matematika nagykövete. A Közgázon, legalábbis az ő idejében, eleve gyakorlat-orientáltabb volt a matek, azóta meg pláne kihullott a fejéből a sok elméleti részlet. Szóval ha valahogyan a látókörébe kerül bármi, aminek köze van a matematikához, akkor tudja, hogy tőlem érdemes érdeklődnie. Ma ebédnél arról kérdezett, hogy mik azok a területei a matematikának, amik kurrensek, pörögnek.

Először persze Perelman és a Poincaré-sejtés jutott eszembe, de rá kellett jöjjek, hogy ez inkább csak egy diszkrét felvillanás, mert amúgy nem nagyon hallani a topológiáról. De van-e olyasmi pervazív téma, mint az előző századfordulón a Hilbert vezette nagy formalizálási törekvés?

Próbáltam a Fields- és Abel-díjak mentén elindulni, de a díjazottak munkásságáról általában nem találtam olyan leegyszerüsített összefoglalót, amit én is értenék. Az egyetlen óvatos következtetés, amit le mernék vonni, az az, hogy az utóbbi évtizedekben gyakoriak az olyan munkák, amik a matematika látszólag egymástól nagyon távoli területeit kapcsolják össze.

Szóval, merre megy a matematika?