{"id":196,"date":"2006-10-27T09:53:56","date_gmt":"2006-10-27T09:53:56","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/10\/27\/prime-number-pathology-fractran\/"},"modified":"2020-02-25T10:57:34","modified_gmt":"2020-02-25T15:57:34","slug":"prime-number-pathology-fractran","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/10\/27\/prime-number-pathology-fractran\/","title":{"rendered":"Prime Number Pathology: Fractran"},"content":{"rendered":"<p>Today&#8217;s pathological language is based on a piece of work called Fractran by John Conway of game theory fame. It&#8217;s a really fascinating bugger; absolutely insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation that I&#8217;ve ever seen. It&#8217;s amazing that this is Turing complete. It&#8217;s not a <em>real<\/em> programming language in the sense of being able to write practical programs; it&#8217;s more of a simple theoretical computational model which has been implemented as a language.<\/p>\n<p>It&#8217;s based on the idea of numbers as products of prime factors. As you should remember from elementary school, every number can be represented by a collection of prime numbers that, multiplied together, produce the number. For a few examples:<\/p>\n<ul>\n<li>\u00a024 = 2\u00d72\u00d72\u00d73, or 2<sup>3<\/sup>\u00d73<sup>1<\/sup><\/li>\n<li>\u00a0291 = 3\u00d797<\/li>\n<li>\u00a01800 = 5\u00d75\u00d73\u00d73\u00d72\u00d72\u00d72=5<sup>2<\/sup>\u00d73<sup>2<\/sup>\u00d72<sup>3<\/sup><\/li>\n<\/ul>\n<p>Conway figured out that using something based on that concept, you can express <em>any<\/em> computable function using nothing but a list of positive fractions.<\/p>\n<p><!--more--><br \/>\nEvery computation takes a single integer <strong>I<\/strong> as input, and operates by repeatedly doing the following:<\/p>\n<ol>\n<li>Set <strong>f<\/strong> equal the first fraction in the list.<\/li>\n<li>Set <em>p=f*I<\/em><\/li>\n<li>If <em>p<\/em> is an integer, then set <em>I=p<\/em>, and go back to step 1.<\/li>\n<li>Otherwise, set <em>f<\/em>\u00a0to the next fraction in the list, and go back to step 2.<\/li>\n<\/ol>\n<p>When you get through the entire list without any of the multiplications producing an integer, then the computation halts.That, my friends, is Turing complete.<\/p>\n<p>Let&#8217;s look at an example. How would you implement basic multiplication in Fractran?<\/p>\n<p style=\"text-align: center;\">\n385\/13, 13\/21, 1\/7, 3\/11, 7\/2, 1\/3<\/p>\n<p>To make it a tad easier to follow, let&#8217;s factorize the numbers that form the fractions:<\/p>\n<p style=\"text-align: center;\">\n(7\u00d711\u00d75)\/13, 13\/(3\u00d77), 3\/11, 7\/2, 1\/3<\/p>\n<p>How is this a multiplication program? If you take any integer <em>I<\/em> which is the product of 2<sup>a<\/sup> and 3<sup>b<\/sup>, then running it through here will produce the number 5<sup>a\u00d7b<\/sup>.<\/p>\n<p>Let&#8217;s try it: take 2<sup>4<\/sup>\u00d73<sup>3<\/sup>=432. It&#8217;ll be easiest to follow if we use the prime factorings.<\/p>\n<ul>\n<li>*I**=2<sup>4<\/sup>\u00d73<sup>3<\/sup>; *f*=385\/13. That won&#8217;t be an integer; 13 isn&#8217;t a factor of **I**.<\/li>\n<li>* *f*=13\/(3\u00d77). That won&#8217;t be an integer, because 7 isn&#8217;t a factor of **I**.<\/li>\n<li>* *f*=3\/11. That won&#8217;t be an integer, because 11 isn&#8217;t a factor of **I**.<\/li>\n<li>* *f*=7\/2. That will be an integer, 2<sup>3<\/sup>\u00d73<sup>3<\/sup>\u00d77.<\/li>\n<li>* **I**=2<sup>3<\/sup>\u00d73<sup>3<\/sup>\u00d77; *f*=385\/13. Not a prime, because 13 isn&#8217;t a factor of **I**.<\/li>\n<li>* *f*=13\/(3\u00d77). That will be an integer; **I**=13\u00d72<sup>3<\/sup>\u00d73<sup>2<\/sup>.<\/li>\n<li>By now, you should have a basic feel for what&#8217;s going on, so I&#8217;m going to start skipping the steps where **I**\u00d7*f* is not an integer.<\/li>\n<li>* *f*=385\/13, **I** becomes 7\u00d711\u00d75\u00d72<sup>3<\/sup>\u00d73<sup>2\/sup&gt;<\/sup><\/li>\n<li>* *f*=13\/(3\u00d77), **I** becomes 13\u00d711\u00d75\u00d72<sup>3<\/sup><span style=\"font-size: 10.5px; vertical-align: super;\">\u00d73.<\/span><\/li>\n<li><sup>* *f*=(7\u00d711\u00d75)\/13, **I** becomes 7\u00d711<sup>2<\/sup>\u00d75<\/sup>2\u00d72<sup>3<\/sup>\u00d73.<\/li>\n<li>* *f*=13\/(3\u00d77), **I** becomes 13\u00d711<sup>2<\/sup>\u00d752\u00d72<sup>3<\/sup>.<\/li>\n<li>* *f*=(7\u00d711\u00d75)\/13, **I** becomes 7\u00d711<sup>3<\/sup>\u00d753\u00d72<sup>3<\/sup>.<\/li>\n<\/ul>\n<p>It keeps going like that. Let&#8217;s analyze it to see what&#8217;s really going on.<\/p>\n<ul>\n<li>the 7\/2 fraction swaps a factor of 2 for a factor of 7. That&#8217;s basically removing a factor of two, which means subtracting 1 from *a*; and then adding in the 7 is keeping track of the fact that we haven&#8217;t yet added *b* to the result to match the subtraction of 1 from *a*.<\/li>\n<li>The 13\/(3\u00d77) rule allows us to start the process of adding *b* to the result. It removes one three, and the placeholder that says we subtracted one from *a*; and adds in a placeholder to say that we&#8217;ve removed one three, but haven&#8217;t finished adding.<\/li>\n<li>the (7\u00d711\u00d75)\/13 rule says that if we&#8217;ve removed a three, we can add one to the exponent of five; and then we also need to add placeholders to continue the addition: we&#8217;ve adding one to the result, but we need to add *b* to the result. So we&#8217;re effectively subtracting one from *b* in order to keep track of the fact that we&#8217;ve done that much of an addition of *b* to the result.<\/li>\n<li>3\/11 says that if the first two rules didn&#8217;t work, then we&#8217;ve finished an addition, we we want to re-add 1 to *b*, in order to restore it to its original value. The other rules have added one 11 for each time we subtracted one from *b*, so this will restore *b*.<\/li>\n<li>Finally, if get get to the 1\/3 rule, it means that we&#8217;ve removed all of the 2s, which means we&#8217;ve completed the multiplication. So we want to remove the *b* leaving the result.<\/li>\n<\/ul>\n<p>Why is this turing complete? It should be pretty easy to see, once you get a sense of what&#8217;s going on. Prime numbers are basically variables &#8211; each prime number holds an integer value (its exponent). The factors of the denominators do two things: subtract values from a variable, and operate as statement guards determining <em>what<\/em> statements are executable. In terms of control flow, the end result is something that&#8217;s actually quite similar to <a href=\"http:\/\/scienceblogs.com\/goodmath\/2006\/10\/pathological_programming_ignor.php\">Version<\/a>. The primes that aren&#8217;t really being used as variables are the complement of the &#8220;ignore&#8221; set.<\/p>\n<p>Evil, huh?<\/p>\n<p>While researching this post, I discovered (via <a href=\"http:\/\/mathworld.wolfram.com\/FRACTRAN.html\">mathworld<\/a>) that Conway figured out a way of writing<br \/>\nan astonishing prime number generator in Fractran. If you take the following sequence as a fractran program, in the numbers that it generates, the exponent on <em>2<\/em> in every number that it generates will always be prime.<\/p>\n<p>17\/91, 78\/85, 19\/51, 23\/38, 29\/33, 77\/29, 95\/23, 77\/19, 1\/17, 11\/13, 13\/11, 15\/2, 1\/7, 55\/1<\/p>\n<p>Definitely the most incomprehensible prime number generator that I&#8217;ve ever seen.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today&#8217;s pathological language is based on a piece of work called Fractran by John Conway of game theory fame. It&#8217;s a really fascinating bugger; absolutely insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation that I&#8217;ve ever seen. It&#8217;s amazing that this is Turing complete. It&#8217;s not [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-196","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-3a","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/196","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=196"}],"version-history":[{"count":2,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/196\/revisions"}],"predecessor-version":[{"id":3835,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/196\/revisions\/3835"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=196"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=196"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=196"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}