Yksinkertaisin mahdollinen tietokone
0
Birminghamilainen opiskelija Alex Smith on voittanut 25 000 USA:n dollarin arvoisen Wolfram 2,3 Turing Machine Research -palkinnon. Palkinnon takana ovat Matematica-ohjelmistosta tunnettu Wolfram Research ja sen perustaja Stephen Wolfram.
20-vuotias Alex Smith kykeni todistamaan, että kahden tilan ja kolmen symbolin Turingin kone on todella yleiskäyttöinen. Todistus päättää puoli vuosisataa kestäneen arvailun yksinkertaisimmasta universaalista Turingin koneesta.
Se antaa myös merkittävän lisätodisteen Steven Wolframin laskennalliselle hypoteesille, jonka hän A New Kind of Science kirjassaan esitti. Vuonna 2002 julkaisemassaan kirjassa hän esitti, että 2,3-toiminen Turingin kone saattaisi olla yksinkertaisin järjestelmä, joka kykenisi toimimaan tietokoneena.
Molekulaarisella tasolla toimiva kone ehkä mahdollinen
Wolfram perusti sen todistamiseksi palkinnon henkilölle tai ryhmälle joka ensimmäisenä todistaa, oliko Turingin kone on yleiskäyttöinen.
Uusimman todistuksen välittömät vaikutukset ovat lähinnä akateemisia. Tulevaisuudessa tulee kuitenkin ehkä mahdolliseksi rakentaa 2,3-toimisella Turingin koneella tietokone, joka operoi molekulaarisella tasolla.
Alun perin Turingin koneen mallin kehitti Alan Turing vuonna 1936 määritelläkseen tarkasti algoritmi-käsitteen. 1950-luvulla Shannon todisti, että kaksi symbolia riittää, kunhan vain tiloja on tarpeeksi.
Käytännön tietokoneen prosessorissa on miljoonia portteja. Matemaatikkoja on kuitenkin kiehtonut kysymys mikä olisi yksinkertaisin mahdollinen Turingin kone? 1960-luvulla ennätykseksi saatiin 7 ja 4. Vuonna 1985 Stephen Wolfram arveli että 2 ja 5 voisi riittää, jonka hänen oppilaansa Matthew Cook myöhemmin osoitti oikeaksi. (Prosessori)
