tag:blogger.com,1999:blog-1489687876525899978.post110469506060525812..comments2010-09-20T10:13:02.094-05:00Comments on Surpassing "Graham's number": A "small" Turing machine whose output exceeds Graham's numberr.e.s.http://www.blogger.com/profile/16798211693065008925noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-1489687876525899978.post-60238200460287766992010-09-20T10:13:02.094-05:002010-09-20T10:13:02.094-05:00I've eliminated another 8 states -- bringing t...I've eliminated another 8 states -- bringing the total now to 64 states -- and added a new posting that describes the resulting machine (GTM64). <br /><br />Four states are eliminated by restricting the rewriting algorithm to ordinals less than ω2 (instead of ω^2), and correspondingly changing the initialisation stage (still with 5 states) to write <0><1><2> onto the all-0 tape. The number computed is now h_(ω+2)(0) + 1 >> G, instead of the unnecessarily-large h_(ω2+1)(0) + 1. This allows blocks q-u to be replaced by simpler code not involving a loop.<br /><br />Four additional states eliminated are c2, e6, l5, and p5, which were superfluous. (The half-state e6 0 had been relabelled as the until-then-unused half-state e4 0, so eliminating e6 frees up the half-state e4 1 to be relabelled as some other unused "half-state", e.g. b1 1.) <br /><br />PS:<br />A notable aspect of this "half-state relabelling" business is that a half-state to be eliminated can be relabelled as any unused half-state that matches it -- anywhere in a TM "program" -- even when there is no "logical connection" between the two half-states being merged into one state; e.g., merging e4 (about pair-reduction) into b1 (about incrementing n). This seriously obfuscates a program merely for the sake of making it smaller. (This reminds me a lot of the goto-laden "spaghetti code" that was more common before the era of "structured programming".) This may help to see why the "logic" of a smallest-program-accomplishing-so-and-so may be virtually impenetrable by human understanding.r.e.s.https://www.blogger.com/profile/16798211693065008925noreply@blogger.comtag:blogger.com,1999:blog-1489687876525899978.post-66626247553552753852010-09-13T09:36:49.837-05:002010-09-13T09:36:49.837-05:00Excellent catch! In addition to the 12 states you ...Excellent catch! In addition to the 12 states you mentioned, it also allows removal of states r and w -- an overall reduction of 14 states. The revised machine, including the final 5-state reduction by reclaiming unused "half-states", has 72 states and reproduces the results of all the previous test cases (with about a 40% reduction in execution time). <br /><br />If you don't mind, I'll simply edit these changes into the above posting and call the revised machine GTM72. <br /><br />Another major reduction seems likely by eliminating the virtual duplication (in blocks v-z) of the (now) 15 states in blocks q-u.r.e.s.https://www.blogger.com/profile/16798211693065008925noreply@blogger.comtag:blogger.com,1999:blog-1489687876525899978.post-5351404159807071512010-09-12T22:45:24.747-05:002010-09-12T22:45:24.747-05:00Hi r.e.s., I'm excitedly analyzing your machin...Hi r.e.s., I'm excitedly analyzing your machine. I like it. You've taken a different approach than I was planning and I think it's been very successful!<br /><br />I have been simulating out using your GTM91 to try to get my head around it and your letterings of the states have been very helpful in breaking up the simulation into chunks.<br /><br />I've only gone over a bit over half of the machine, but I believe that you can cut at least 7 states (maybe 12 states).<br /><br />Consider:<br /> d1 0 0 R d2 <br /> d1 1 1 R d1<br /> d2 0 0 L e1<br /> d2 1 1 R d3<br /> d3 0 0 L d1<br /> d3 1 1 L d1<br /><br />as far as I can tell, d3 only appears in these last three lines and thus you can actually cut out d3 and change the ref d3 -> d1. Why? Because, the only way you can end up in d3 is from (d2 1 1 R d3) which means you're in this configuration:<br />d3 ?? 1 (?) ?? which (no matter what ? is) goes to:<br />d1 ?? (1) ??? which goes to:<br />d1 ?? 1 (?) ??<br /><br />So, you could have just gone (d2 1 1 R d1) in the first place.<br /><br />This looks like it will also work for f3, q3, h3, j3, k3, m3 (and glancing back at the transition table: maybe x3, v3, s3, g3 and even e3->f1)Shawn Ligockihttps://www.blogger.com/profile/03500286688026953185noreply@blogger.com