- Mike Pilat brought this to the attention of Lance Fortnow.
- Lance Fortnow brought it the attention of Bill Gasarch.
- Bill Gasarch brings this to your attention.
If you haven't already heard, my employer, Stephen Wolfram (and Wolfram Research) this week announced a $25,000 prize to prove or disprove that a particular 2-state, 3-color Turing Machine is universal (i.e., Turing-complete). If proven, it would be the simplest possible UTM. The details of the prize and the Turing Machine in question are all here. I thought you and your students might find this challenge interesting.Is this interesting? Does offering $25,000 make it interesting? INTERESTING/NOT INTERESTING THINGS ABOUT TURING MACHINES:
- Are these numbers interesting in their own right. For UTM NO, mostly because it is tied to a particular machine model. For Ramsey/VDW the numbers might be useful to inform conjectures. The few known values of VDW indicate that the VDW numbers may be far lower than the bounds given by the proofs.
- Has nice math come out of the attempt? For UTM no, For Ramsey very little- R(4) uses Field Theory.
- Has nice computer science come out of the attempt? For UTM/R/VDW the answer is yes- clever tricks and such. But (I think) nothing that can be used outside of these problems. If I'm wrong the commenters will politely correct me.
- Why do people climb Mount Everest? Because its there! Finding these numbers may have the same mentality; however, its much safer.