{"id":248,"date":"2022-04-05T19:06:00","date_gmt":"2022-04-05T19:06:00","guid":{"rendered":"https:\/\/groups.cs.umass.edu\/equate-ml\/?p=248"},"modified":"2022-04-07T18:14:05","modified_gmt":"2022-04-07T18:14:05","slug":"paper-turing-completeness-of-bounded-precision-recurrent-neural-networks","status":"publish","type":"post","link":"https:\/\/groups.cs.umass.edu\/equate-ml\/2022\/04\/05\/paper-turing-completeness-of-bounded-precision-recurrent-neural-networks\/","title":{"rendered":"Paper: Turing Completeness of Bounded-Precision Recurrent Neural Networks"},"content":{"rendered":"\n<p>Previous works have proved that recurrent neural networks (RNNs) are Turing-complete. In the proofs, the RNNs allow for neurons with unbounded precision, which is neither practical in implementation nor biologically plausible. To remove this assumption, we propose a dynamically growing memory module made of neurons of fixed precision. We prove that a 54-neuron bounded-precision RNN with growing memory modules can simulate a Universal Turing Machine, with time complexity linear in the simulated machine\u2019s time and independent of the memory size. The result is extendable to other stack-augmented RNNs. Furthermore, we analyze the Turing completeness of both unbounded-precision and bounded-precision RNNs.<\/p>\n\n\n\n<div class=\"wp-block-buttons is-layout-flex wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link\" href=\"https:\/\/neurips.cc\/Conferences\/2021\/Schedule?showEvent=27999\">Paper<\/a><\/div>\n<\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Previous works have proved that recurrent neural networks (RNNs) are Turing-complete. In the proofs, the RNNs allow for neurons with unbounded precision, which is neither practical in implementation nor biologically plausible. To remove this assumption, we propose a dynamically growing memory module made of neurons of fixed precision. We prove that a 54-neuron bounded-precision RNN &hellip; <a href=\"https:\/\/groups.cs.umass.edu\/equate-ml\/2022\/04\/05\/paper-turing-completeness-of-bounded-precision-recurrent-neural-networks\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Paper: Turing Completeness of Bounded-Precision Recurrent Neural Networks&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":177,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[32,34,26],"class_list":["post-248","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-ai-ml","tag-32","tag-neurips","tag-paper","group-blog","hfeed"],"_links":{"self":[{"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/posts\/248","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/comments?post=248"}],"version-history":[{"count":1,"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/posts\/248\/revisions"}],"predecessor-version":[{"id":249,"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/posts\/248\/revisions\/249"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/media\/177"}],"wp:attachment":[{"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/media?parent=248"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/categories?post=248"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/groups.cs.umass.edu\/equate-ml\/wp-json\/wp\/v2\/tags?post=248"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}