Why does research on the busy beaver function get funded?

Question

I saw this video about the busy beaver function and looked at the applications section of the Wikipedia article about the busy beaver function.

I concluded that there is zero practical or even theoretical value in searching these numbers S(n) : n > 5. Now in the video the person says, that people are using supercomputers to calculate S(5). Now I assume using supercomputers is expensive and so somebody is obviously funding this research.

Am I too narrow minded to see the value of funding such research and there is actual value to it or what other reasons are there to fund such endeavors? I assume most academic research is funded by taxes and so it should bring some value to society. While there might be some intellectual value in having such knowledge, does the cost justify it?

PS: Probably this question is too broad/opinion based, but I didn't know on what SE site it would fit best or how to improve it to make it less opinion based, feel free to edit.

EDIT: The economic question is partially solved, by supercomputers being much cheaper than I thought so that argument falls flat. Still could somebody give me a hint on what the value of such research is?

Answer 1

Extremely likely, this concrete example is useless. So is any other concrete example. However, there are many of these examples, and we do not know which handful of them will be useful.

Some ancient people wasted time on research in number theory, some of which ended up being practically useful. Some studied motion of stars in detail far exceeding calendaring and navigational needs. This also proved useful.

Many, many studies also led to dead-ends. At the time, one could not tell which of them would.

Answer 2

The busy beaver function is an important artifact of computability theory- in particular it's known to (asymptotically) grow faster than any computable function. Intuitively this means that it is a "harder" sequence to compute than all computable sequences.

Thus, it gives rise to a new kind of proof by exhaustion. Suppose you were to write a Turing machine program P to test all possible special cases of a proof (potentially an infinite number of cases). If the program finds a problem with the proof, then it will halt. Otherwise, it will run forever. By the definition of the busy beaver machine, if the Turing machine P halts, then it will halt sooner than the busy beaver machine with the equivalent number of states. Thus, all we have to do to prove our theorem is to run our program for the specified number of steps, and if it doesn't halt before our busy beaver machine then we're guaranteed that it will never halt, and indeed there can be no contradictions of any special case to our proof.

Using this fact isn't feasible on current computer hardware, but that's rarely been a roadblock to this kind of research. If our concept of computer hardware or software were revolutionized and such a task could be completed then this would be a systematic approach to proving or disproving many outstanding questions in many fields. One of the purposes of this kind of research is to spur new questions, not to provide new answers.

When it comes to computing S(5) in particular, the challenge is a basic research challenge. Pure research is about solving problems that have never been solved, it's not about having some great application. Nobody has yet devised a way to compute S(5), and since this sequence is not computable it's possible that there is no way to effectively compute this number. Being able to compute it, or to give a reason why it can't be computed, would probably be a publishable result- both are hard, and neither have been done before.

As a practical exercise it's a good application of computability theory and a counterpoint to the halting problem. The halting problem shows us that there is no single algorithm that can tell us whether any arbitrary program halts, but it's often possible to tell whether a specific program will halt. The analysis of S(3) and S(4) required in-depth analysis by experts to determine whether certain Turing machines with 3 and 4 states actually halted or not. That's not really possible with S(5), so tackling this problem requires asking other questions like "what classes of programs can we determine whether they halt or not?".

To see this more clearly, try this blog post by MIT's Scott Aaronson. A student of his proved that the 8000th busy beaver number is unknowable by standard set theory. Mathematics and logic cannot compute this number, even given unlimited time and space. Here's a very obvious and very deep question that nobody can answer: Why is it the case that we can know S(1), S(2), S(3), and S(4) relatively easily, we can't say whether we can know S(5), and we can say for certain that we can't know S(8000)? If you could tell us the answer to that you'd have the attention of a whole lot of smart people. Endeavoring to do the hard work of computing S(5) is a step in understanding this.

Is S(8000) the first such element in this sequence that is unknowable? If not, what's the smallest element?

Two notes: I'm not a theorist, so all of this is my interpretation. Take it with a grain of salt. Second, a better venue for this question would be the Computer Science stack exchange. They love this stuff over there.

Answer 3

Let me give a guess, which might not be accurate for this case but which has a more general range.

If one tries to compute S(5) by brute force, that is probably not more interesting (but much longer) than solving any given Sudoku by brute force with a computer. But the point of such a question is precisely that, being difficult, if one hopes to answer it one needs to try being smart. One needs to find smart ways to be able to skip as much computations as possible compared to a brute force approach. In this process, one will probably learn something about the involved objects (e.g. Turing machines) and understand them better. One will also have to be smart with the details of the implementation, with the multi-threading, etc.

We choose to go to the Moon. We choose to go to the Moon in this decade and do the other things, not because they are easy, but because they are hard, because that goal will serve to organize and measure the best of our energies and skills, because that challenge is one that we are willing to accept, one we are unwilling to postpone, and one which we intend to win, and the others, too. (JFK 1962)

Answer 4

Research like this tends to open doors. You never ever know what discoveries will be built on them in future. Many, many crucial modern discoveries come from research that didn't seem to have any practical use at the time.

So funding it has really practical benefits, over and above those due to "gaining pure knowledge" - especially if you target which to fund or explore based on what it might relate to. It's like an investor investing in start-ups. Not every idea goes anywhere (yet) but given support, a proportion will... and a few will become worlds-changers.

Radio waves are a good example of a discovery thought to be completely useless for practical purposes - look up what Hertz though of their practical uses. Could he have foreseen a world of radio media in every pocket, radio emergency teams and work crews coordinating, mobile phones, satnav, radar, microwave ovens, remote space missions and exploratory cameras, Google Earth, and WiFi, would he have thought this?

Ditto quantum theory - surely discussing the arcane ideas of not just atoms but quarks and smaller particles, not to mention assuming that they can do weird things like exist and not exist in different places or one place at the same time, is a useless hypothetical debate about atoms and hypothetical smaller sub-particles too small to be relevant to everyday life, if anything is. Fast forward 50 years - the semiconductor. Supermagnets. Superconductors. MRI scanners in hospitals. Your smartphone. Undersea cables. The laser. CD/DVD/Bluray. The internet. Almost every computing device and optical cable in widespread use today. Anything else that uses (or needs to take into account) quantum tunnelling and other weird behaviours.

Ditto the odd crackling of silk rubbed on amber (electricity), the seemingly random number sequences generated by elliptic forms and modular entities (the Modularity Theorem and Fermat), tables of logarithms and trigonometric values (tabulated values were used used by pre-computer age mathematicians, and may have seemed pointless to some, but without them would Kepler, Galileo, Newton and others have made all of the discoveries they did?) Mendel spent years crossing peas; a pointless and obsessive waste of effort, until you fast forward to genetics, understanding DNA, gene therapy, disease resistant rice, mitochondrial disease treatment, heredity when it starts to look a bit more significant in human history.

Mathematically, the same holds true. One difference is that you sometimes have to calculate your data rather than just observe it. But the principle is very similar and so is the impact.

It's also quite likely that this is seen by those in the know as an "interesting" problem, one likely to not be entirely a dead end or which is linked somehow to other intractable problems.

Answer 5

I concluded that there is zero practical or even theoretical value in searching these numbers S(n) : n > 5.

Perhaps wrongly. Euclid first studied the primes over 2000 years and they didn't have a concrete application until a few decades ago (cryptography).

Anyways, if you're looking for a real answer, I'd suggest you read some of the papers on the subject. The wikipedia page lists a few.

Answer 6

I completely agree with the mathematicians and physicists in the audience who have pointed out that pure math has in the past sometimes led to important practical advances. While this happens very rarely, it’s utterly impossible to know which will be the rare gem ahead of time so you have to fund lots of ultimately-useless (or, more accurately, useless-so-far) research if you want to have a chance to find said gems. As an engineer, I am familiar with a lot of those past gems, and would not be able to do my job at all if they hadn’t happened. I certainly have neither the skillset nor the temperament to have found those discoveries myself!

That said, as an engineer, there is another aspect to consider: building supercomputers is hard. The simple engineering practice of building the computer to do this may lead to improvements and discoveries itself, and even if it doesn’t, funding this engineering means you have that many more people with that much more experience doing things. This is important, and very, very frequently overlooked.

A recent question on Aviation Stack Exchange asked why modern military aircraft take so long to produce compared the military aircraft of decades past (after all, those aircraft also had to break new ground and solve extremely difficult challenges, using much more basic tools, and the difference in time is nearly an order of magnitude). There are, of course, many reasons, but this answer in particular stood out to me by emphasizing the importance of having a highly-experienced engineering workforce:

Experienced engineers back then had worked on a dozen new designs (or more), so they had developed a gut feeling how to design the next one. Today, one can be lucky to have brought a single one into the air within a lifetime.

That answerer recounts how he had actually lobbied his company to do a quick, cheap design just to give the engineers more practice and more experience doing a real-world design, that having better engineers would be worth the cost of an entirely artificial exercise (it should come as no surprise that this project did not get green-lit).

Does the fact that a few more people have built one more supercomputer equal the cost of them doing so? I don’t know—but it’s a non-negligible thing, and should be considered in the cost–benefit analysis. Particularly from the perspective of a nation—having skilled engineers is such an obvious advantage to a nation that I suspect very few would object to the general concept of taxes going towards having better engineers.

Answer 7

By definition, science is not about having value.

Science is about accumulating and organizing knowledge.

This applies not only to the busy beaver problem, but also to the digits of Pi, the digits of the Euler's number, the string theory in physics, and the sex life of Amphicoelias fragillimus.

Answer 8

Even if a theoretical problem has no applications (yet), the techniques developed to tackle it and the knowledge acquired along the way can be immensely valuable and potentially useful even in seemingly unrelated areas. One can look to the history of mathematics for examples of this.

Aside from this, I'm going to add a potential application of tackling the busy beaver problem: Solomonoff induction. In short, Solomonoff induction is a theory of general inductive inference based on weighing hypotheses according to the size of Turing machines that produce them. Theoretical formalisms for artificial general intelligence like AIXI are based on it.

Tackling the busy beaver problem is also relevant to areas like inductive programming (automatically constructing computer programs) and automated theorem proving, since it involves proving properties (e.g. halting or non-halting) of arbitrary computer programs. See Computer Runtimes and the Length of Proofs, for example.

Answer 9

To extend the answers with another perspective: the fundamental question that theory of computability asks is "what kind of functions are computable, given some simple, sensible assumptions and given models of machines that could be instantiated in the physical universe?" (I mean, "instantiated" in theory, with some practical caveats, of course.)

So one way how to look at the theories of computability and computational complexity is to view them as being about some fundamental properties of the world. Why are some functions computable and some are not, given the standard model of physics? What is computable in the lifetime of the universe and what is not? What makes quantum computers possible, and what are their ultimate limits? What kind of computers could we expect if physics were slightly different? What kind of assumptions one needs to make for hyper-computation to be possible?

It is therefore possible that these theories aim to uncover something as deep and fundamental as theoretical physics. Under this analogy, investigation of whether the Busy Beaver function with argument "5" is computable could be compared with a single specific experiment about the properties of some esoteric particle. It gives a little bit of insight in some fundamental nature of things.

Answer 10

The Busy Beaver problem/game has provided a very tangible application in its contribution to deciding the halting time of a very large set of small Turing machines that, in turn, are used to calculate an empirical distribution as an approximation to the so-called Universal Distribution that allows the estimation of the algorithmic probability of a string (that is the probability to produce a string with a random computer program whose executable bits are the result of e.g. tossing a coin).

Such distribution has been called miraculous in the past (Google The miraculous universal distribution). This is because of its theoretical properties as the most powerful general purpose predictor. In the work of the Algorithmic Group and the Algorithmic Dynamics Lab that I co-lead together with the help and contribution of several brilliant researchers, the Busy Beaver has contributed to produce these numerical approximations of algorithmic probability and has made impact in areas such as animal and human cognition, graph complexity, evolutionary biology, artificial life, and molecular biology. Here a few pointers (only 2 with URLs because Academia does not let me add more links, the others you can Google):

• Algorithmically probable mutations reproduce aspects of evolution such as convergence rate, genetic memory, modularity, diversity explosions, and mass extinction
• Human Behavioral Complexity Peaks at Age 25 (there was a lot of hype in the media about it, and there is a video in YouTube explaining the results in a very simple, kind of oversimplified, fashion)
• Methods of Information Theory and Algorithmic Complexity for Network Biology Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks

In turn, that research has triggered theoreticians to update their work too! e.g. this paper:

• A probabilistic anytime algorithm for the halting problem

Among many others, including a Physica A article on graph complexity and a Seminars in Cell and Developmental Biology paper on applications to molecular biology and genetic networks.

This is because the Busy Beaver is deeply related to concepts in Algorithmic Information Theory such as the Chaitin Omega number and the so-called Solomonoff's-Levin's distribution (see the Scholarpedia article).

So, all the way from a completely theoretical 'game' to real-world applications in the context of the most pressing problems of science!

Answer 11

Complex number theory projects often get approved because they might possibly have some cryptographic benefit. Much work has been done on one-way functions and calculations that require considerable computer resources. An concrete example is modulus of a prime exponent in a finite field used in RSA public key cryptography.

Also, much of the research in cryptography is classified. There might be a reason this project was approved that is known only to the researchers and the people approving the project.

Answer 12

Some research might open up unforeseeable opportunities in its sister fields. Implementation of extremely efficient busy beaver systems (as it is quite time consuming) might have implications in some other important simulations. I am not saying busy beaver problem has no value, but others has pointed those out quite well.

This type of cross benefit occurs in open source systems as well. I remember explicitly that the research that is done on Linux to improve battery life of Android devices has led to a substantial cost savings on supercomputers running on Linux as their major cost is electricity.