63

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?

  • 1
    Comments are not for extended discussion; this conversation has been moved to chat. – StrongBad Jun 16 '17 at 14:43
  • 3
    Somewhat related to the question "What's the point?" and Busy Beaver/_Computable numbers: scottaaronson.com/writings/bignumbers.html - fascinating tour of this area. – Stilez Jun 17 '17 at 12:26
  • 4
    Can I reject the premise? I'd love to see a grant number here, showing that funding is actually spent on this problem. Most mathematics research is done on the professor's own time, without any funding at all. Even if a supercomputer is used, they can 'nice' this compute time down so that 'more important' problems are given priority, making the marginal cost of the compute essentially zero. – user14717 Jun 19 '17 at 19:38
  • Fascinating read @Stilez . – Hakaishin Jun 20 '17 at 11:59

12 Answers 12

154

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.

  • 178
    +1. A fun story: British mathematician G. H. Hardy famously wrote in 1940 in his essay A Mathematician's Apology, "No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years." Within 5 years, number theory had been used to crack the Engima cipher (today it forms the foundation of public-key cryptography) and the theory of relatively was used to develop atomic weapons. Today's pointless research is tomorrow's textbook knowledge. – tonysdg Jun 14 '17 at 21:27
  • 8
    I seem to recall I read a long time ago that Hardy, in the early 1900s, was involved in a discussion where he proposed to eliminate groups from the math curriculum as they were not very useful. – Martin Argerami Jun 14 '17 at 22:21
  • 16
    @tonysdg Atomic weapons were developed using quantum theory, not relativity. Relativity is required for the GPS system, and I guess that has military applications? – jpmc26 Jun 15 '17 at 8:28
  • 6
    @OrangeDog The law was changed under Bill Clinton to afford both civilian and military GPS the same level of accuracy. This was called Selective Availability and the civilian GPS signal was intentionally degraded. – David Jun 15 '17 at 13:27
  • 26
    @jpmc26: If I'm reading this Wikipedia page correctly, the idea of mass-energy equivalence arose from Einstein's paper on special relativity. This is directly applicable to nuclear weaponry. But I think you're 100% correct in that general relativity didn't necessarily carry practical value until much later (with the rise of the technologies you mentioned). – tonysdg Jun 15 '17 at 22:02
89

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.

  • 10
    Generally interesting response, but it should not contain an evaluation of the asker's mind. I do get irritated every time when somebody asks what the value of a seemingly irrelevant (but scientifically very interesting) question is, but it would never occur to me to judge their attitude, and do my best in taking the question as legitimate. – Captain Emacs Jun 15 '17 at 7:32
  • 13
    @CaptainEmacs, the asker does use exactly the rheotical question "am I too narrow minded" in his question, which David flagged in his answer by saying "in your words". – KraZug Jun 15 '17 at 8:37
  • 2
    @KraZug True, but still, I think it is better not to use the askers' own words against them. Again, I like the general answer, with very useful and interesting links, that's why taking this personal evaluation off (even if it seems sanctioned by OP) it would make it even better. – Captain Emacs Jun 15 '17 at 8:55
  • 1
    @CaptainEmacs Sure, valid points. – David Jun 15 '17 at 12:54
  • 1
    @KraZug The problem lies in the anwer of "yes". The answer to "am I too narrow minded" in this case is not "yes", it is "no". Narrow-minded means "Having restricted or rigid views, and being unreceptive to new ideas." and the very fact the OP is asking this question shows that they are receptive to new ideas and thus are not narrow-minded. – Pharap Jun 16 '17 at 2:37
29

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)

  • 5
    I don't think you can solve S(5) using only brute force as such. Computing S(5) involves showing that some Turing machines never halt. To say that the brute force approach to showing that a Turing machine never halts takes "much longer" is a bit of an understatement ;) – gmatht Jun 18 '17 at 11:02
14

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.

  • «Could he have foreseen » wireless telegraphy should have been an obvious idea, and others thought so. radar might have occured to a futurist as a possibility, since Maxwell's equations were already agreeing with measurements on the speed of such waves and the eclipse timing of Jupiter’s moons showed that transit time can be significant. So ask Verne, not Hertz, what the future might do with it. – JDługosz Jun 18 '17 at 23:07
  • "Might" has always been a province of futurists and writers. But this question looks more at what might be termed hard pragmatists. It should have been, but hindsight helps to distinguish fantasy from possibility. At the time, Hertz was probably more typical even if he didn't have to be. – Stilez Jun 19 '17 at 8:14
9

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.

  • 5
    They also kick-started a huge part of equation solving techniques, number theory, and they also link to many other areas of mathematics which have real world applications. Sometimes it's what a thing does directly. Other times the big practical payoffs are what it triggers tangentially while being worked on. If you want to really find what a toolkit can do, sometimes the best way is to find a really, really intractable problem and try working out how on earth to make some inroad into it..... – Stilez Jun 15 '17 at 15:05
9

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.

  • 3
    Very interesting point and as you said often overlooked. I haven't thought about that but it makes sense. – Hakaishin Jun 16 '17 at 17:24
5

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.

3

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.

3

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):

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!

  • I am amazed every day what great answers are posted on se. Thank you very much for your time and this amazing anwser, I will definitely check out the links. – Hakaishin Sep 18 '17 at 6:37
3

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.

1

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.

1

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.

  • 1
    Why would anyone downvote this? It answers the question, does not repeat anything that is said and it is absolutely true. – Cem Kalyoncu Jun 18 '17 at 18:04
  • 2
    I think this is a good answer... but/and I suspect that some people just downvote when they're in a cranky mood. – paul garrett Jun 18 '17 at 18:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.