-
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.
Mike's letter to Lance:
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:
INTERESTING: Turing Machines and seemingly unrelated models of computation are equivalent. NOT INTERESTING: Details of those equivalences. (They were clever and
interesting at the time, but not now.)
INTERESTING: There is a Universal Turing Machine. NOT INTERESTING: Finding the smallest one.
INTERESTING: Turing Machines seem to capture all things that are computable. While usually called Church's thesis or The Church-Turing Thesis, Bob Soare thinks is should be Turing's thesis. See Springer LNIM, No. 4497,
Computability in Europe, or just get it
here.
INTERESTING: HALT is undecidable.
INTERESTING: The Busy Beaver Function (see also this) grows faster than any computable function, and hence is not computable. NOT INTERESTING: The actual values of this function. Especially since they would be tied to a rather particular type of Turing Machine (e.g., 1-tape, 2-symbol).
Is the size of the smallest UTM or the values of the Busy Beaver function interesting to know for their own sake? How does this compare to finding actual Ramsey Numbers (see Dynamic Survey on Small Ramsey Numbers) or actual
VDW numbers What are the criteria of interest?
-
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.
I think you are missing a few points here.
ReplyDeleteFrom a CS point of view maybe its not interesting to know where the boundary of universality is, eg, how simple the machines can get. But for natural science, its a lot more relevant -- a system with 6 rule cases is more likely to occur naturally than one with 20. And undecidability in natural systems is most certainly interesting. (This is also a relevant point for technology... suppose you want a universal molecular computer, you want its rules to be as simple as possible.)
Is the encoding interesting? If your universal machine is big and complicated, then no, because its details are arbitrary. If your machine is the smallest possible, the encoding is a lot more meaniningful, because its a lot less arbitrary and hacky.
At the values themselves interesting? Well, that depends on if you care about more computation, or more about mathematics. We know that undecidabilty implies that to find out what a program actually does, you need to run the program. If you don't, its like trying to do biology just by theorizing about the DNA, without looking at the actual organisms premeating our planet.
As far as connections to other systems, simple turing machines certainly do connect to plenty of other topics, from mathematics to computation.
If you look back at old issues of J. ACM in the late 1950's and early 1960's this kind of stuff was typical fodder. Marvin Minsky had paper on a 6-state 7-symbol UTM which was followed by 8-state and 6-state 5-symbol UTMs in a 1961 J. ACM paper by Watanabe...
ReplyDeleteI always thought that it was a very positive sign that the field had moved beyond this.
In my opinion the field itself is definitely very interesting. There are quite a number of open questions that are concerned with small universal Turing machines, etc. As with a lot of CS theory, many of the questions are (subjectively, I suppose) interesting in their own right. Furthermore, to answer point 3 of the post, there are connections (due to Maurice Margenstern and Pascal Michel) to the 3x+1 problem.
ReplyDeleteBill, your qn. (2) is perhaps the important one ("has good math come out of it"?)... i.e., the journey is what is more interesting than the actual target, sometimes.
ReplyDeleteThere is also an element of timeliness here... first we proved that graph k-colorability is npc, then that 3-colorability is npc, quickly realized that 2-colorability is ptc, then started hunting for the smallest f(n) such that coloring a 3-colorable n-vertex graph with f(n) colors is npc, etc, etc. The technology involved in all of this ranged from cute to clumsy to downright deep. AFAIK, the current state of art is that coloring a 3-colorable graph with k colors (for some constant k known only to khot) is npc. It may well be that thirty years from now, some incredibly energetic discrete-math-hacker proves that k=13 is achievable and some twenty further years later, someone hacks away more to get k=6. Would they still be interesting? Not likely unless the technology developed is interesting and/or new in its own right.
Is the collatz conjectur interesting? It isn't all that far removed from these small busy beaver number questions.
ReplyDeleteBram: to me the Collatz conjecture (and similarly the odd greedy Egyptian fraction problem) are interesting as examples of how little we know about proving that algorithms terminate. I don't particularly care whether the Collatz conjecture is true or false, but if it does turn out to be provably true I think I would likely care about the techniques needed to prove it.
ReplyDeleteAs for the prize question, I'm not very excited by it, mostly because I don't think Turing machines are particularly compelling either as a model of real computers or as a simplified discrete model of physical law. (The RAM or Boolean circuits do better at the former, cellular automata at the latter). But it's still possible that exploring the boundary of what's computable could lead to interesting techniques.
To follow up on the points of Anon 1: a UTM that is easier to describe is not necessarily one that is easier to implement in nature. In fact, biological organisms exhibit "evolutionary problem kernelization," where a simple decision that has to be made quickly ("I want to eat that" vs. "Run like hell") comes from highly sophisticated hardcoding/preprocessing, whether from the bat's sonar, the squid's eye, or the cilia of the paramecium.
ReplyDeletePerhaps the (2,3)-TM is indeed universal but requires exponential blowup of input size relative to UTM's that are larger. If so, there seems to be no inherent gain for the design of a molecular computer.
However, if finding a smaller/the smallest UTM translates to an absolute lower bound for kernelization of problems that every biological organism -- or nanorobot -- must solve, then it seems like a big deal to me. I know little about the relation between kernelization and computability theory, and would appreciate any followup comments.
Perhaps the (2,3)-TM is indeed universal but requires exponential blowup of input size relative to UTM's that are larger. If so, there seems to be no inherent gain for the design of a molecular computer.
ReplyDeleteThis scenario could be true, but is probably unlikely as Woods and Neary have shown that all known universal Turing machines are polynomial time simulators. See, for example, the last paragraph of the guest post on this blog by Janos Simon for details: FOCS Funding, Music and Talks.
If it were an irresistably interesting problem, SW wouldn't have to post a $25K reward.
ReplyDeleteIf you just want something that is easily simulatable in nature, just use the game of life. Much simpler rules than any of 1D UTMs, albeit with the catch you have to use 2D.
ReplyDeleteAnd 2/3D is more "natural" for nature anyway.
"If it were an irresistably interesting problem, SW wouldn't have to post a $25K reward"
ReplyDeleteAnd the millenium problems are correspondingly 40 times less interesting.
The flip-side question is certainly interesting: For which [classes of simple] discrete digital systems M is the prediction problem
ReplyDeleteINPUT: A configuration I of M, a number t >= 0
OUTPUT: The configuration J = M^t(I) that results after t steps by M from I
is solvable? Universality makes it unsolvable. One can ask if it's feasible when t is given in binary, or in NC when t is in unary.
Cris Moore has two nice papers (first two in the Cellular Automata section of his pubs page) giving NC algorithms (unary t) for cellular automata M whose rules have certain algebraic properties. This ICALP'06 paper by (Damien) Woods and (Turlough) Neary, related to their FOCS'06 paper mentioned by Anon#8, shows that prediction is P-complete for the Rule 110 cellular automaton, on account of its being feasibly universal.
Let me define "M is [feasibly] universal" in a way that hopefully remedies the technical vagueness in the official Wolfram contest specification. Take a "standard" universal TM U as your benchmark, just like when defining (time-bounded) Kolmogorov complexity. Then say M is feasibly universal if there is a polynomial-time computable 1-1 map f and a polynomial q such that for all valid configurations I,J of U and t >= 0:
() f(I) and f(J) are valid configurations of M;
() J = U^t(I) ==> for some r <= q(|I|+t), f(J) = M^r(f(I));
() J is never reached from I ==> f(J) is never reached from f(I).
The definition can be tweaked by requiring r <= q(t) alone, by weakening the 1-1 condition on f, and in other ways. The main point is to separate feasibility of the mapping (i.e., "encoding") from that of the simulation.
Woods told me last month that whether "Rule 30" is universal is still open. I have a possibly-related question to pose when I finally get time to polish some scribe notes from my DNA+cellular computing seminar this past term. Finally, a motivation for small universal [non-TM] systems is John Tromp's effort to minimize concrete overhead for Kolmogorov complexity. (I guess Scott A. would call this a Woitian comment---is it worth the link time?)
Check that: Universality makes the analogous halting problem unsolvable. I chose not to mention it or how Woods-Neary and Matthew Cook define universality/prediction. The extra "is" following the problem statement is another artifact of editing things out.
ReplyDeleteAnd the millenium problems are correspondingly 40 times less interesting.
ReplyDeleteNo, they have a different purpose. The point of Wolfram's prize is to get people to work on this problem when they otherwise wouldn't have. That way Wolfram can point to the resulting papers as evidence for the impact of NKS. To accomplish this, the prize has to be larger than any other that might be comparably easily obtained (which it is). The point of the Clay prizes is not to provide motivation to solve the problems (anyone who solves one will have put in far more effort than a million dollars warrants), but rather to tie Clay's name to the problems, so that nobody will ever discuss the Poincare conjecture without talking about Clay. To accomplish this, the prize has to be impressively large, on the scale of a lottery prize.
Thanks very much Ken Regan for your informative comments.... And, speaking of problems that are only 1/40th as interesting, when are you guest-blogging about Mulmuley's new 138-pg paper connecting P!=NP to the Riemann Hypothesis over finite fields? :-)
ReplyDeleteWow, Aaron, thanks! I hadn't known about any paper after "Geometric Complexity Theory 3" in the series---papers 4--11 are all March 2007 or later. I'll have a go at them; indeed my recent PhD graduate Dr. Maurice Jansen and I have some prior impetus to do so this summer. Meanwhile, this survey by V. Lakshmibai from mid-2005 goes a little further than mine.
ReplyDeleteTo answer your question only somewhat facetiously, the answer is: I did so earlier today! :-). The Riemann-related work by Pascal Koiran I referred to there is available here. The best recent place to start is Peter Bürgisser STACS'07 paper, third on his group's pubs page here. Neither paper is cited by Mulmuley---rather, he goes back to earlier connections found by Deligne (et al.) in his work on the Weil conjectures.
Hi,
ReplyDeleteI work on small UTMs and related things, along with my colleague Turlough Neary. Mostly we are concerned with theoretical questions about time/space complexity and program size. I think the field is not only interesting, but fascinating. Below, I mention a few things that I think are interesting, and some applications. Some include points already made by others in previous comments (e.g. Anon 1 & Ken Regan).
- Characterising the complexity of problems associated with simple universal models. (Example application: due to their syntactic simplicity, such models are good candidates for embedding into other systems to prove hardness results).
- Characterising the complexity of problems associated with simple non-universal models. (Example application: such models can be used to place upper bounds on the power of other models via simulation).
- Applying simple/small machines to natural models of computing. The above two ideas are particularly useful for finding small and simple nature-inspired computers. Perhaps this might lead to nature-inspired computers which are easy and cheap to build in the lab., etc. There are a quite number of papers that apply small UTMs and related research in this way. Furthermore, we now know that many such constructions lead to small computers which are time & space efficient.
- Finding new tricks to write programs that are (extremely) program-size efficient. (Example application: Its great fun.)
- Proving universal program size lower bounds for small/simple machines. (Again such bounds can be applied to systems outside the field of small UTMs.)
- As mentioned by others above, there are links with things like the Collatz conjecture and related problems, tilings, syntactic properties (besides size) of Turing machines programs and other models, etc.
Besides the above examples, there are probably many others. Furthermore there are some personal, non-scientific, reasons why I think its an interesting area. Everyone believes that their own research is interesting, so it is really quite pointless to go into this here.
There have been a steady drip of papers with new ideas since the early days of Shannon, Minsky, Ikeno, Watanabe, but I'll not go into those here either. Finding small programs, and proving that none exist, is interesting in my view. However there are also other, more subtle, goals which will hopefully have impact with some. I really think that the field has something interesting to offer researchers in other fields (e.g. by finding connections to complexity theory and other areas).
Damien Woods
What is the smallest "undecidable" Turing machine: the smallest one for which we can prove neither that it halts nor that it runs forever?
ReplyDeleteThere's no mathematical truth to be uncovered by searching for the smallest one -- in fact, you'll never know you've found it, since it's impossible to prove any Turing machine is undecidable. And of course, which one is the smallest depends on your formalism for the machines.
But wouldn't it still be fun to find the first one that you can't decide, despite all your efforts, and wonder "Is it you?"
I thought you be interested to know who won: a 20-year old engineering student named Alex Smith.
ReplyDeleteThe write-up in Nature is here
and Stephen Wolfram's blog entry on it is here.
Smith's proof is here.