Here's my alternative history steampunk novel proposal:<p>What if Turing was such a minimalist engineer instead of a great mathematician, that he decided not to include a "halt" instruction, because you could always just terminate a program with an infinite loop: Bang! One fewer instruction! Less is more, worse is better, RISC is more efficient, right? Just emulate halt in software! The Woz would be proud.<p>But as it turned out in this universe, halt was the one instruction you needed to express the halting problem, the foundation of modern computer science! The looping infinitely problem would be moot, because all programs would always loop infinitely!<p>His genius was to add that one little magical thing that otherwise could have been missing: the halt instruction.<p>Kind of like Hamilton, who fruitlessly tried to multiply triples, which his children tormented him relentlessly about, until he finally realized he was missing a magical dimension, invented quaternions, and vandalized a bridge, all in the same day.<p><a href="https://en.wikipedia.org/wiki/History_of_quaternions" rel="nofollow">https://en.wikipedia.org/wiki/History_of_quaternions</a><p><a href="https://en.wikipedia.org/wiki/Broom_Bridge" rel="nofollow">https://en.wikipedia.org/wiki/Broom_Bridge</a>
In case you think you've figured out the 2-state solution and you want to check that you can't do better, I've uploaded the number of 1s your machine should output at <a href="https://modalduality.org/static/busy-beaver-2.txt" rel="nofollow">https://modalduality.org/static/busy-beaver-2.txt</a>, but did not include the actual configuration.
Just some food for thought. The reason that the busy beaver challenges are enormously difficult to do manually, for higher number of allowed states, is because of two things:<p>self-modification and fixed points<p>A turing machine has no understanding of code vs memory. You can scratch out turing machines in their tape form, and simply write a program in C and restrict the memory to a couple of ints and also use labels to write to the code section. This is more practical and still an excercise in how you can use the code as memory once you are certain it is past execution.<p>But even more clever is having the fixed points of your printing routine be actual equal to NEW instructions written to the code section. Then you begin to truly treat the pc program like a turing machine and push the boundaries of how many operations you can perform before halting.<p>Now..about fixed points. By fixed point I really just mean a point at which the behavior of a program switches into a different context or ultimately the point at which the program finally halts (necessary for the challenge.)<p>Lets assume we have byte variables, A and B<p>We can print 1s quite naively doing this:<p>A = 0
B = 0<p>while A++
while B++
print "1";<p>We would get 256*256 = 65536 prints<p>But we can extract way more if we use the code section. And we can extract even more if we come up with fixed points / conditions other than just all our variables wrapping back around to 0. Ie. using number theory with each variable as a modulus, we can stop on much rarer conditions.. such as primes that are 1 mod 5, 2 mod 7, 3 mod 11, etc..Essentially, the entire world of coincidental structure and things that appear to be true but may just have very very large outliers..can be exploited to keep on looping. For some examples, take a look here: <a href="https://www.quora.com/What-are-some-mathematical-theories-that-were-accepted-and-later-proven-wrong" rel="nofollow">https://www.quora.com/What-are-some-mathematical-theories-th...</a><p>Literally if you can write a function that counts which is greater, li(x) or pi(x), and returns true or false. Then you just do while(liCmpPi(BigNum(allMyMemory).increment()) print(1)<p>you will have more prints than the universe has atoms. more than the seconds in the universe until heat death. math is fun :-(
Cool idea!<p>There were a couple points in the explanation which were kind of unclear to me, though:<p>What makes it okay to identify the <i>naming</i> of a large number with producing that large number of things (e.g. 1's)? This felt like a disconnect to me since in the introduction we are asked the largest number we can write down in 15 seconds, but my understanding is that the Busy Beaver functions aren't 'naming a number', but instead we're counting the number of 1's output by them (or maybe the function returns the number of ones rather than the string itself?). Actually, I think I'm starting to see the connection now: if we're considering the mathematical function rather than an executing program, then it just 'instantaneously' gives back a single number, and that single number is whatever sequence of ones the Turing machine would produce, which we could interpret as a reference to a numeric value rather than counting the digits? Maybe still a bit lost. Another way of stating my confusion: a person could easily write down a number larger than the number of 1's output by the 7-state solution (102*10^10^10^1870532) within 15 seconds (I could write that number down in maybe 5 seconds or so)—so in what sense is the Busy Beaver function naming a larger number?<p>There was another thing that tripped me up for a while, though I think I get it now, which was: what characterizes the Busy Beaver function? Is it that it "returns the maximum of the running times of all programs of length n that do eventually halt"—or is it that it "counts the number of 1's possible to be written by an n-state Turing machine before it halts"? It's pretty clear to me now that it's the latter, and that the former (the BBS function) is just one implementation of the general concept, but it gave me some trouble to figure that out.
What are the most practical applications of the biggest numbers, like cryptography?<p>Inversely, what are the most practical applications of the smallest numbers?