tag:blogger.com,1999:blog-3722233.post6192502742401802596..comments2019-10-14T12:11:35.608-04:00Comments on Computational Complexity: $25,000 prize for ... Univ TMLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger19125tag:blogger.com,1999:blog-3722233.post-53944134806715313162007-10-24T09:42:00.000-04:002007-10-24T09:42:00.000-04:00I thought you be interested to know who won: a 20-...I thought you be interested to know who won: a 20-year old engineering student named Alex Smith.<BR/><BR/>The write-up in Nature is <A HREF="http://www.nature.com/news/2007/071024/full/news.2007.190.html" REL="nofollow">here</A><BR/><BR/>and Stephen Wolfram's blog entry on it is <A HREF="http://blog.wolfram.com/2007/10/the_prize_is_won_the_simplest.html?lid=title" REL="nofollow">here</A>.<BR/><BR/>Smith's proof is <A HREF="http://www.wolframscience.com/prizes/tm23/TM23Proof.pdf" REL="nofollow">here</A>.Kathryn Cramerhttps://www.blogger.com/profile/15531290922967396395noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11420959968732700202007-05-24T17:46:00.000-04:002007-05-24T17:46:00.000-04:00What is the smallest "undecidable" Turing machine:...What is the smallest "undecidable" Turing machine: the smallest one for which we can prove neither that it halts nor that it runs forever? <BR/><BR/>There'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.<BR/><BR/>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?"Andrewhttps://www.blogger.com/profile/02903366372812261992noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86656300563235323992007-05-23T14:57:00.000-04:002007-05-23T14:57:00.000-04:00Hi,I work on small UTMs and related things, along ...Hi,<BR/><BR/>I 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). <BR/><BR/>- 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).<BR/><BR/>- 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).<BR/><BR/>- 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.<BR/><BR/>- Finding new tricks to write programs that are (extremely) program-size efficient. (Example application: Its great fun.)<BR/><BR/>- Proving universal program size lower bounds for small/simple machines. (Again such bounds can be applied to systems outside the field of small UTMs.)<BR/><BR/>- 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.<BR/><BR/>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.<BR/><BR/>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).<BR/><BR/> Damien Woodsdamienhttps://www.blogger.com/profile/02797278560724806484noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43890362917116233502007-05-22T17:43:00.000-04:002007-05-22T17:43:00.000-04:00Wow, Aaron, thanks! I hadn't known about any pape...Wow, 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, <A HREF="http://www.math.cas.cz/~pudlak/alg-geom/GCTlectures.1.5.pdf" REL="nofollow">this survey by V. Lakshmibai</A> from mid-2005 goes a little further than mine. <BR/><BR/>To answer your question only somewhat facetiously, the answer is: I did so <A HREF="http://scottaaronson.com/blog/?p=240#comment-11852" REL="nofollow">earlier today!</A> :-). The Riemann-related work by Pascal Koiran I referred to there is available <A HREF="http://citeseer.ist.psu.edu/25366.html" REL="nofollow">here</A>. The best recent place to start is Peter Bürgisser STACS'07 paper, third on his group's pubs page <A HREF="http://math-www.uni-paderborn.de/agpb/papers.html" REL="nofollow">here</A>. 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.KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34494746220628483612007-05-22T12:06:00.000-04:002007-05-22T12:06:00.000-04:00Thanks very much Ken Regan for your informative co...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? :-)Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51870174205924532742007-05-22T11:27:00.000-04:002007-05-22T11:27:00.000-04:00And the millenium problems are correspondingly 40 ...<I>And the millenium problems are correspondingly 40 times less interesting.</I><BR/><BR/>No, 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3022311114961430762007-05-22T08:49:00.000-04:002007-05-22T08:49:00.000-04:00Check that: Universality makes the analogous halti...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.KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55637567399894987022007-05-21T23:33:00.000-04:002007-05-21T23:33:00.000-04:00The flip-side question is certainly interesting: F...The flip-side question is certainly interesting: For which [classes of simple] discrete digital systems M is the <I>prediction problem</I><BR/><BR/>INPUT: A configuration I of M, a number t >= 0<BR/>OUTPUT: The configuration J = M^t(I) that results after t steps by M from I<BR/><BR/>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.<BR/><BR/>Cris Moore has two nice papers (first two in the Cellular Automata section of his <A HREF="http://www.santafe.edu/~moore/pubs.html" REL="nofollow">pubs page</A>) giving NC algorithms (unary t) for cellular automata M whose rules have certain algebraic properties. <A HREF="http://www.bcri.ucc.ie/~dw5/download/dw15.pdf" REL="nofollow">This ICALP'06 paper by (Damien) Woods and (Turlough) Neary</A>, related to their <A HREF="http://arxiv.org/abs/cs.CC/0612089" REL="nofollow">FOCS'06 paper</A> mentioned by Anon#8, shows that prediction is P-complete for the <A HREF="http://en.wikipedia.org/wiki/Rule_110_cellular_automaton" REL="nofollow">Rule 110 cellular automaton</A>, on account of its being feasibly universal. <BR/><BR/>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 <I>feasibly universal</I> if there is a polynomial-time computable <B>1-1</B> map f and a polynomial q such that for all valid configurations I,J of U and t >= 0:<BR/><BR/>() f(I) and f(J) are valid configurations of M;<BR/>() J = U^t(I) ==> for some r <= q(|I|+t), f(J) = M^r(f(I));<BR/>() J is never reached from I ==> f(J) is never reached from f(I).<BR/><BR/>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.<BR/><BR/>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 <A HREF="http://homepages.cwi.nl/~tromp/cl/cl.html" REL="nofollow">effort to minimize concrete overhead for Kolmogorov complexity</A>. (I guess Scott A. would call this a <A HREF="http://scottaaronson.com/blog/?p=240" REL="nofollow">Woitian</A> comment---is it worth the link time?)KWReganhttps://www.blogger.com/profile/09792573098380066005noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84227113096693200302007-05-21T21:12:00.000-04:002007-05-21T21:12:00.000-04:00"If it were an irresistably interesting problem, S..."<I>If it were an irresistably interesting problem, SW wouldn't have to post a $25K reward</I>"<BR/><BR/>And the millenium problems are correspondingly 40 times less interesting.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88994153649890624442007-05-21T20:51:00.000-04:002007-05-21T20:51:00.000-04:00If you just want something that is easily simulata...If 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.<BR/><BR/>And 2/3D is more "natural" for nature anyway.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14357595054403874942007-05-21T19:53:00.000-04:002007-05-21T19:53:00.000-04:00If it were an irresistably interesting problem, SW...If it were an irresistably interesting problem, SW wouldn't have to post a $25K reward.Brian Hayeshttp://bit-player.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36013986759403691322007-05-21T19:28:00.000-04:002007-05-21T19:28:00.000-04:00Perhaps the (2,3)-TM is indeed universal but requi...<I>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.</I><BR/><BR/>This 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: <A HREF="http://weblog.fortnow.com/2006/10/focs-funding-music-and-talks.html" REL="nofollow">FOCS Funding, Music and Talks</A>.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33388266299295957122007-05-21T18:52:00.000-04:002007-05-21T18:52:00.000-04:00To follow up on the points of Anon 1: a UTM that i...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. <BR/><BR/>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.<BR/><BR/>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.Aaron Sterlingnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44763288410358386372007-05-21T18:21:00.000-04:002007-05-21T18:21:00.000-04:00Bram: to me the Collatz conjecture (and similarly ...Bram: 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.<BR/><BR/>As 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.D. Eppsteinhttp://11011110.livejournal.com/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60662331334625698052007-05-21T17:10:00.000-04:002007-05-21T17:10:00.000-04:00Is the collatz conjectur interesting? It isn't all...Is the collatz conjectur interesting? It isn't all that far removed from these small busy beaver number questions.Bram Cohenhttp://bitconjurer.org/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75594940165988435982007-05-21T17:02:00.000-04:002007-05-21T17:02:00.000-04:00Bill, your qn. (2) is perhaps the important one ("...Bill, 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.<BR/><BR/>There 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.D. Sivakumarhttps://www.blogger.com/profile/05750992965116762335noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52743315321060288342007-05-21T16:59:00.000-04:002007-05-21T16:59:00.000-04:00In my opinion the field itself is definitely very ...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74157759639038636022007-05-21T15:59:00.000-04:002007-05-21T15:59:00.000-04:00If you look back at old issues of J. ACM in the la...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...<BR/><BR/>I always thought that it was a very positive sign that the field had moved beyond this.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35695771782902918032007-05-21T14:06:00.000-04:002007-05-21T14:06:00.000-04:00I think you are missing a few points here.From a C...I think you are missing a few points here.<BR/><BR/>From 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.)<BR/><BR/>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.<BR/><BR/>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. <BR/><BR/>As far as connections to other systems, simple turing machines certainly do connect to plenty of other topics, from mathematics to computation.Anonymousnoreply@blogger.com