Stephen Wolfram, yg bikin Mathematica dan penulis buku "A New Kind of Science" men-teorikan bahwa 2,3 Turing Machine itu universal.
Kemudian dia bikin kompetisi berharga U$$ 25,000 untuk siapa saja yang bisa membuktikan kalo 2,3 Turing Machine itu universal.
Apa itu Turing Machine? Konsep yang dijabarkan oleh matematikawan hebat, Alan Turing, tentang komputer. Kalo John Nash di-film-kan dengan "A Beautiful Mind", Alan Turing di-film-kan dengan "Enigma". Seru deh film-nya...
Intinya Turing Machine itu model sebuah komputer, ada tape (seperti memory), ada head buat baca tape (seperti CPU baca instruksi), ada action table (seperti kode software), dan ada state register (seperti register komputer).
Nah, kalo Universal Turing Machine (UTM) itu adalah Turing Machine yang bisa mensimulasikan Turing Machine lainnya.
Intinya apa sih? Kalo bisa di-implement di UTM, berarti bisa dibuat software-nya.
Sebelum bukunya, selama 40tahun hanya terbukti UTM yang paling simple punya 7-state dan 4-color. Sedangkan di bukunya "A New Kind of Science", Pak Wolfram membuktikan UTM yang paling simple itu 2-state dan 5-color.
Nah, sekarang telah dibuktikan oleh Alex Smith, mahasiswa 20thn dari Birmingham, UK bahwa UTM yang paling simple adalah 2-state, 3-color. Baca blog Wolfram tentang menangnya Alex Smith disini:
http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html
Ngefek-nya dimana? Ya dengan berkembangnya molecular biology, ini berarti cukup dengan molekul yang bisa meng-emulasikan 2-state dan 3-warna, kita bisa menjalankan aplikasi apa saja! Ya, itu termasuk menjalankan Windows (tentunya masalah efisiensi adalah hal lain).
Ini karena dalam Computer Science ada Church-Turing Thesis: "any real-world computation can be translated into an equivalent computation involving a Turing machine."
Wow, congrats Alex Smith.... waktu gw umur 20thn, gw lagi ngapain ya? :)