## Wednesday, October 24, 2007

### Wolfram (2,3) machine exists

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.

(via BB)

1. Also note: Scott Aaronson is now apparently the person to ask for a quote on any TCS-related matter. :)

2. the 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"