Kahekümneaastane Birminghami Ülikooli tudeng võttis vastu ühe maailma tuntuima elava matemaatiku väljakutse ja lahendas 2,3 Turingi masina universaalsuse küsimuse.
Alex Smith asus Stephen Wolframi pakutud ülesannet lihtsa arvutusmehhanismi universaalsusest lahendama niipea, kui sellest internetifoorumist luges. Matemaatik ja ettevõtja (muu hulgas arvutialgebra paketi Mathematica looja) Stephen Wolfram esitas väljakutse tõestada 2,3 Turingi masina universaalsus isiklikust huvist lihtsate süsteemide kompleksse käitumise vastu. Väike hulk primitiivseid reegleid väheste objektide jaoks võib kaasa tuua süsteemi, kui terviku, üllatavalt keeruka käitumise. Turingi masin on üks näide sellest, teda võib kujutleda kui ruudulist paberit, kus alguses on esimese rea igal ruudul mingi väärtus, mis määrab etteantud reeglite kohaselt järgmise rea ruutude väärtused jne. Uue rea kirjutamine on omamoodi arvutustehe, mitme rea täitmine järjest vastab pikemale rehkendusele. Universaalne masin suudab põhimõtteliselt lahendada mistahes algebraülesande. 2,3 Turingi masina korral saavad ruudud olla ühes kolmest võimalikust olekust, mille muutmiseks on kaks erinevat operatsiooni.
Siin tähistab üles või alla suunatud must tilk ruudu värvimise operatsiooni, mille valiku ja seega ruudu värvi järgmisel real määrab vertikaalsihis samal kohal paikneva ruudu ja tema naabrite värv eelmisel real.
Alex Smith tõestas 40 leheküljel (pdf), et niisugune süsteem on samaväärne juba teadaolevalt universaalse märgirea algebraga (Wikipedia: Tag System). Lisaks tunnustusele autasustati teda 25 000 USA dollariga.
Allikas: Nature
Toimetas Erik Randla