Tardos Gábor Gödel-díjas !!!!!
Eredeti szerző: jotunder
A Gödel-díj a számítógéptudomány egyik legnagyobb díja, és 2020-ban Tardos Gábor kapta meg Robin Moserrel a Lovász Lokál Lemma konstruktív bizonyításáért.
Az eddigi magyar Gödel-díjasok: Babai László, Szegedy Márió (kétszeres), Tardos Éva (Gábor nővére), Lovász László, és remélem a pozsonyi Róbert Szelepcsényi nem fog megharagudni, ha őt is beveszem.
Azért álljon itt néhány másik név is: Alexander Razborov, Daniel Spielman, Peter Shor, Shafi Goldwasser, Noga Alon, Avi Wigderson, Madhu Sudan. Ők is Gödel-díjasok.
Ez is Magyarország, nemcsak az izék.
<div class='sharedaddy sd-block sd-like jetpack-likes-widget-wrapper jetpack-likes-widget-unloaded' id='like-post-wrapper-192691293-16518136-6adf180ff22c0' data-src='https://widgets.wp.com/likes/?ver=14.1#blog_id=192691293&post_id=16518136&origin=www.orulunkvincent.hu&obj_id=192691293-16518136-6adf180ff22c0&n=1' data-name='like-post-frame-192691293-16518136-6adf180ff22c0' data-title='Like or Reblog'><h3 class="sd-title">Like this:</h3><div class='likes-widget-placeholder post-likes-widget-placeholder' style='height: 55px;'><span class='button'><span>Like</span></span> <span class="loading">Loading...</span></div><span class='sd-text-color'></span><a class='sd-link-color'></a></div>
Gratulálunk a díjazottnak. Ahogy az amcsi filmekben mondják: Szép munka!
(A Róbert szlovákul is hosszú ó, tehát szerintem lehet nyugodtan Róbert Szelepcsényi nek írni.)
@jan: javítottam.
Pach János nyert egy Advanced ERC-t, szóval ez a hét elég jól néz ki a Rényinek :))))
Huh, hatalmas gratula!
Ha Razborovot és Tardos Évát megemítjük, akkor érdemes már Márk Jerrumot is, ő 1996-ban kapta meg. Alistar Sinclair-rel a Markov láncos munkáikra, de Jerrumot itt most azért említeném, mert volt Snirrel egy méltatlanul nem ismert cikke ’82-ben, bőven Razborov előtt.
Az amúgy magyarul számítástudomány, csak mondom.
@közösperonos átszállás: ma reggelig az volt, de kijavítottam számítógéptudományra. 🙂
@jotunder: Hmm. Olyasvalakiként, akinek van köze a számítógéphez, meg a hozzá kapcsolódó tudományhoz is, a számítástudományhoz viszont nem igazán, az a véleményem, hogy: kár volt.
(A honlapjuk, meg ha ez számít, a Wiki is azt mondja, hogy a Gödel prize a „theoretical computer science” területén kiosztott díj. Amit itthon „számítógéptudománynak” hívhatunk, az meg elsősorban az az ág, amely a skála „practical” végén van, és ez (folytatva képzavaromat) a theoreticalnál sokkal-sokkal vastagabb.)
@közösperonos átszállás: az ELTE tanszeket szamitogeptudomanyinak nevezik es szerintem ott azert a kombinatorika iranyu computer science a tipikus.
de a lenyeg az, hogy nekem sokkal jobban tetszik a szamitogeptudomany szo a szamitastudomanynal. 🙂
@jotunder: az Akadémia hármas osztályán Informatika- és Számítástudományi Bizottság van.
Azonfelül egy számítástudomány elméletbe nagyon egyszerűen bele tudod pakolni a nem-determinisztikus Turing gépeket, egy számítógéptudományiba csak nyögvenyelősen. Vagy mondjuk számítógéptudományi elméletben teljesen inadekvát olyan elméleti eredményekről beszélni, ami egy gyakorlatban használt számítógépen soha nem fog lefutni galaktikus időnél rövidebb időben, míg egy számítástudományban ez természetes.
Vagy mi a helyzet a Turing-ekvivalens számítási modellekkel? Az mindenképpen számítástudomány, de számítógéptudomány lenne?
Persze ezek ettől még csak nevek, amelyek legfeljebb egy józan paraszti ész szerinti definíciót sugallnak, ettől még definiálhatsz bármit, ha rögzíted. Az idősebb Tusy nevezi pl. konzekvensen a számítógépet is számológépnek, így nyugodtan hívhatod te is a számítástudományt számítógéptudománynak, ha az jól esik neked 🙂 vagy egy huszárvágással akkor már számológéptudománynak 🙂
@jotunder: @Egon Estragon: Úgy nézem, ez ilyen tájszólás-dolog lesz, mert valóban, az ELTÉ-n vagy mondjuk Debrecenben Számítógéptudomány, Szegeden meg a BMÉ-n inkább Számítástudomány, néha meg vegyes.
Én azért tartom sokkal megalapozottabbnak a számítástudományt, mert a számítógéptudomány azt sugallja, hogy ez a számítógép tudománya, és hát ugye lószart. 🙂 Az informatikusok (azaz, ugye, számítógéptudósok) erősen túlnyomó többsége nem is hármas osztály, hanem hatos (műszaki), anno a Bolyai-szerződésemnél az MTÁ-s ügyintéző hölgy is fejből vágta arra, hogy informatika, hogy hatos osztály (és tényleg).
Ezt már régen meg akartam kérdezni, hogy matematikából hogyan lehet ERC (vagy bármilyen) grant proposalt írni? Merthogy kémiából, biológiából, de még történettudománytól is, gondolom, le lehet írni, hogy ha elnyerem a grantet, akkor ezekkel és ezekkel a módszerekkel, ezeket és ezeket a témákat fogom kutatni, ezeket a kísérleteket végzem el, ezeket a levéltárakat dolgozom fel stb., és amire jutok, azt publikálom. Nyilván az ideális az, ha valami érdekesre jutok, de ha nem, azt a nem-érdekes dolgot is le tudom tenni mint eredményt.
Ehhez képest meg, legalábbis én így képzelem, a matematikában sejtések vannak, na és akkor a grant proposalba azt írja az ember, hogy ezt és ezt a sejtést próbálom bebizonyítani, na de mi van, ha nem sikerül bebizonyítani? Szóval valahogy úgy érzem, hogy a matematikában nem úgy van, hogy megyek előre, olvasom, kijegyzetelem, kísérletezek, lemérem, megírom és valami tuti lesz a végén, hanem vagy kijön a bizonyítás, vagy nem…
Aztán lehet, hogy tök másként van, teljes kívülállóként spekulálok erről…
@jan: egy ilyen projekt egy irányt jelöl ki, általában kimondanak pár erősebb sejtést, ami nincs reménytelenül messze attól, amit a PI addig csinált, vagy ha reménytelenül messze van, legalábbis bizonyos szögből nézve eladható az, hogy abban az irányban lehet valamit csinálni. nem kevés olyan proposal van, ahol tudható, hogy a konkrétan vállalt nagyobb sejtésekből egyet sem fognak megcsinálni, de a vége az, hogy lesz harminc egészen jó cikk a csoportban. általában olyan embereknek adják az ilyen grantot, akik nagyon cool dolgokon gondolkoznak elég régen, és sok eredményük van erős folyóiratokban.
@jotunder: értem, köszi!
@jan: Egy jó matematikusnak nem csak azt kell megtanulnia, hogyan legyenek zseniális gondolatai (ezt persze kevéssé lehet tanulni, de valamennyire azért lehet), de azt is, hogyan találja meg (találja ki) azokat a problémákat, amik a lehető legérdekesebbek, legmélyebbek azok közül, amiket ő meg tud csinálni. Az előbbit nem annyira lehet előrejelezni, még sok év eddigi munka alapján se, de az utóbbit sokkal inkább igen. Ha tehát az eddigi pályafutás elég erős, a proposal pedig elég izgalmas, és van valami egyéni íz benne, ami arra ad reményt, hogy ezeket pont a PI tudhatja megcsinálni, mert úgy áll hozzá, ahogy más nem, ahogy csak ő tud, akkor az lehet a nyerő.
@Mister Gumpy: köszi!
kicsit más: és vajon hol tartanak a szorgalmas rivjúerek a kvázi-poli idejű gráf-izomorfizmus tétellel. azért az szép lehet, ha vki 66 éves korában megtalálja azt a bizonyítást, amit 50 éve kutat.
@tamtkr: tavaly jelent meg az Asterisque-ben Helfgott Bourbaki előadása, ami után ez az eredmény gyakorlatilag peer-review-ednak számít.
@jotunder: Kérdezhetek ennek kapcsán is egyet? Ha jól értem, Helfgott a gyenge Goldbach-sejtést bizonyította be, és a gyenge Goldbach-sejtés egészen triviálisan következik az erős Goldbach-sejtésből.
Mégis, ha jól olvasom, rengeteg matematikus rengeteg energiát rakott a gyenge-Goldbach bizonyításába, ebből tehát arra következtetek, hogy az az általános vélekedés, hogy az erős Goldbachot majd csak 50, 100 év múlva fogjuk bebizonyítani, vagy lehet, hogy soha? Hiszen ellenkező esetben, ha elérhető közelségben lenne az erős Goldbach, akkor minek vesződni a gyenge Goldbachhal?
Erről pedig eszembe jutott egy régi tűnődésem, még középiskolában gondolkoztam ezen, hogy vajon minden igaz állítás bebizonyítható-e? Tehát az van-e, hogy ha eleget töri elég sok ember a fejét mondjuk az erős Goldbach sejtésen, akkor előbb-utóbb rátalál a bizonyításra. Vagy lehet, hogy vannak igaz, de nem bizonyítható állítások? (Nem tudom, van-e persze értelme ilyen filozofikus szinten gondolkodni erről.)
jan: „egy régi tűnődésem, még középiskolában gondolkoztam ezen…”
igen, ezen én is. És még a szóbanforgó díj névadója is, ő egyébként ilyesmikre jutott: en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem
@jan:” Erről pedig eszembe jutott egy régi tűnődésem, még középiskolában gondolkoztam ezen, hogy vajon minden igaz állítás bebizonyítható-e? „
a goldbach-sejtésről konkrétan nyilván nem fogok semmit mondani, de … az egy olyan sejtés, ami a peano-aritmetika egyik formulájának igazságtartalmára vonatkozik. mit jelent az, hogy „igaz” egy ilyen formulára? két definíció van. az egyik pont az, hogy „bizonyítható”. a másik rafináltabb. a peano-aritmetikának vannak különböző modelljei, ezek” fake természetes számok”, minden, ami a peano-aritmetikában kell, ott van rajtuk, minden axióma teljesül. egy ilyen modellben megkérdezheted, hogy pont az adott formula igaz-e vagy nem? ha minden modellben teljesül, akkor az egy másik „igaz” definíció. Gödel azonban bebizonyította, hogy ez a két definíció ekvivalens.
vannak olyan állítások, amelyek bizonyos modellekben igazak, bizonyos modellekben meg nem. ezek a független állítások.
persze feltételezzük, mivel nem a Mátrixban élünk, hogy az aritmetika axiómarendszere ellentmondásmentes. vannak olyan állítások, amelyek hétköznapi értelemben igazak, de amúgy függetlenek, ezek azok, amelyek úgy bizonyíthatók, hogy nemcsak a számelmélet axióma rendszerét használjuk, hanem mindent, amit máskor szoktunk használni, azaz a teljes halmazelméletet. általában nem szoktuk vizslatni azt, hogy egy bizonyításban használjuk a halmazelmélet axiómáit vagy ragaszkodunk az aritmetikához. nagyon sok matematikai bizonyítás lép ki (általában csak látszólag) az aritmetikai nyelvből. van olyan állítás, ami hétköznapi értelemben igaz (Goodstein Tétel), de tisztán aritmetikai úton nem bizonyítható (van olyan modellje a Peanonak, amiben nem igaz) ez a Paris-Kirby modell. maga a PA ellentmondásmentessége is igaz ZFC-ben (persze ZFC ellentmondásmentessége meg ZFC-ben nem bizonyítható). az, hogy PA ellentmondásmentessége független azt jelenti, hogy van olyan modellje a számelméletnek, amelyben nem igaz a CON(PA) formula. ez volt az a pont, amikor feladtam a logikát. aztán elmagyarázták nekem, hogy a CON(PA) hamisságának bizonyítása csak azt jelenti, hogy van egy Gödel-száma ennek az állításnak, és az a Gödel-szám kicsit „nagy”.
@jotunder: Köszi! Nem mondom, hogy minden részét értettem, de amit értettem, az is elég érdekes volt 🙂
@jan: A logikai részbe (eldönthető vagy eldönthetetlen) csak picit belekontárkodva: amikor a Goldbach-sejtésen gondolkodunk, azt a természetes számok „standard” modelljében tesszük, a gyenge (három prímes) változat bizonyítása is tekintélyes mennyiségű analízist tartalmaz.
Ami a számelméleti részt illeti, a következőről van szó. Amikor az n páros (illetve páratlan) számot akarjuk felírni két (illetve három) prím összegeként, akkor konkrét felírások keresgélése helyett azoknak a számát próbáljuk megbecsülni, úgymond, azt megmondani, hogy statisztikailag mennyire igaz a Goldbach-sejtés egy konkrét n-re, tehát hogy az n=p+q (illetve n=p+q+r) egyenletnek hány p, q prím (illetve p, q, r prím) megoldása van. A megoldásszámhoz a [0,1] szakasz minden pontja hozzájárul valamennyit (sajnos bizonyos pontok negatívan), és azt szeretnénk látni, hogy az össz-hozzájárulás pozitív (akkor ugyanis biztosan van megoldás). Az derül ki, hogy azoknak a pontoknak a hozzájárulását könnyű nagy pontossággal megmondani, melyek nagyon közel vannak kis nevezőjű racionális számokhoz (ezek alkotják az úgynevezett „nagy ívet”), míg a kis nevezőjű racionális számoktól távol eső pontok (melyek a „kis ívet” alkotják) hozzájárulását csak megbecsülni tudjuk. Röviden, a
megoldásszám = nagy ív járuléka + kis ív járuléka
formulában a nagy ív ad valami pozitívat, a kis ív pedig ad valami rejtélyeset. A gyenge Goldbach-ban már 80 éve tudták, hogy a kis ív járuléka (abszolút értékben) kisebb, mint a nagy ívé, tehát nem tudja annyira lehúzni a megoldásszámot, hogy hirtelen egy megoldás se legyen. Legalábbis feltéve, hogy n nagyobb, mint valami fix, jó nagy szám. Innentől ez elvileg egy számítógépes feladat: ellenőrizzünk le mindent addig a fix, jó nagy számig. A valóságban a fix, jó nagy szám számítógépekkel is elérhetetlen (több, mint 6 millió számjegye van), és ezt a „meddig kell leellenőrizni” korlátot húzták lejjebb és lejjebb sokan és kemény munkával. Közben persze a számítógéppel elérhető tartomány is megnőtt. Helfgottnál találkozott össze ez a kettő: 30-jegyű számokig számítógéppel ellenőrizve, felette pedig a megoldásszám-formulából adódott a gyenge Goldbach.
Az erős változatban az romlik el (és ez is régen ismert), hogy a nagy ív hozzájárulása túl kicsi, a kis ív hozzájárulását nem elég megbecsülni, pontosabban kell kiszámolni. Biztosan lényeges, új ötlet kell… vagyis hát az persze mindig is kellett, de itt olyan ötlet kell, ami fenekestül fordítja fel a világot, mert az eddigi megközelítések akkor sem adnak semmit, ha a prímek eloszlásáról olyan egyenletességet tételezünk fel (ez egy fontos összetevő a nagy ív járulékának kiszámolásában), amit például az általánosított Riemann-sejtés adna.
@Ménkűnagy Bundáskutya: köszi!
a
index.hu/techtud/2020/04/12/kinai_koronavirus_meghalt_john_conway_matematikus_gyasz/
@ámbátor: amit nem írtak le az az, hogy a huszonhat sporadikus véges egyszerű csoport közül hármat Conway fedezett fel. filozófiai szempontból azt hiszem ez a legnagyobb dolog.
@jotunder: Ehhez még annyit tennék hozzá, hogy „sporadikus véges egyszerű csoport” keresésre a google nekem a wikipédia után másodiknak ezt találta:
orulunkvincent.blog.hu/2015/02/09/az_ertelmiseg_esete_a_veges_egyszeru_csoportok_klasszifikaciojaval
@ámbátor: conwayt beleírtam valamiért.
@ámbátor: Most esett le, Life-ot még én is játszottam egy csomót. RIP akkor tőlem is.
Annyira.
xkcd.com/2293/