{"id":151,"date":"2007-05-16T06:07:18","date_gmt":"2007-05-16T10:07:18","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=141"},"modified":"2007-05-16T06:07:18","modified_gmt":"2007-05-16T10:07:18","slug":"operations-research-and-turing-machines","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2007\/05\/16\/operations-research-and-turing-machines\/","title":{"rendered":"Operations Research and Turing Machines"},"content":{"rendered":"<p>From <a href=\"http:\/\/science.slashdot.org\/article.pl?sid=07\/05\/15\/2253218\">slashdot.com<\/a>:<\/p>\n<blockquote><p> \t\t\tAn anonymous reader writes <em>&#8220;Stephen Wolfram, creator of Mathematica and author of <a href=\"http:\/\/www.wolframscience.com\/\">A New Kind of Science<\/a>, is offering a <a href=\"http:\/\/www.wolframprize.org\/\">prize of $25K<\/a> to anyone who can prove or disprove his conjecture that a particular 2-state, 3-color Turing machine is universal. If true, it would be the simplest universal TM, and possibly the simplest universal computational system. The announcement comes on the 5-year anniversary of the publication of NKS, where among other things Wolfram introduced the <a href=\"http:\/\/www.wolframscience.com\/nksonline\/page-707\">current reigning TM champion<\/a> \u2014 &#8216;rule 110,&#8217; with 2 states and 5 colors.&#8221;<\/em><\/p><\/blockquote>\n<p align=\"left\">Operations research (particularly integer programming) seems relevant to this work (through things like the undecidability of integer quadratic programming).  $25,000 anyone?<\/p>\n","protected":false},"excerpt":{"rendered":"<p>From slashdot.com: An anonymous reader writes &#8220;Stephen Wolfram, creator of Mathematica and author of A New Kind of Science, is offering a prize of $25K to anyone who can prove or disprove his conjecture that a particular 2-state, 3-color Turing machine is universal. If true, it would be the simplest universal TM, and possibly the &hellip; <a href=\"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2007\/05\/16\/operations-research-and-turing-machines\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Operations Research and Turing Machines&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[],"class_list":["post-151","post","type-post","status-publish","format-standard","hentry","category-challenges"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/151","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=151"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/151\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=151"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=151"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=151"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}