Back in May, Bill and David discussed the new Wolfram challenge: Show that a particular 2-state 3-color TM is universal. Apparently, this question has now been resolved affirmatively, by Alex Smith, an undergraduate at the University of Birmingham.
Read more about here, and here.
(via BB)
Also note: Scott Aaronson is now apparently the person to ask for a quote on any TCS-related matter. :)
ReplyDeletethe proof seems to have spawned some controversy. In particular, the proof allows the tape to be initialized with infinite non-repeating sequence of bits, begging the question of what exactly it means for a TM to be "universal"
ReplyDeletehttp://cs.nyu.edu/pipermail/fom/2007-October/thread.html#12156