James' World 2

Click the link below the picture

.

Most people probably don’t think of mathematics when they hear “busy beavers.” But these eager little animals symbolize one of the most amazing concepts of the knotty field: not everything can be calculated, no matter how hard you try (or how busy of a beaver you are). The busy beaver function is the first example of a noncalculable mathematical expression. The function itself is easy to explain: it refers to the largest number of steps a computer program can take before stopping if the program has n states, where states refer to the complexity of the problem. But its values, called BB(n), will never be known for all quantities of n. Mathematicians and theoretical computer scientists have long pondered at which n mathematical tools fail: Where exactly is the limit of what can be calculated?

For more than 40 years, many experts assumed that BB(5) could lie beyond this limit of computability and would therefore be unattainable. But now an international collaborative project called the Busy Beaver Challenge has succeeded in determining the value of BB(5), and its calculation was formally verified by a computer-aided proof assistant. According to the new research, the magic number for BB(5) is 47,176,870, meaning that a program with five states can take a maximum of 47,176,870 steps before halting—or it will never halt at all. The last big “busy beaver” achievement occurred in 1983, when the late computer scientist Allen Brady proved that BB(4) equals 107.

Busy beavers are deeply rooted in the foundations of mathematics. In the 20th century, many experts dreamed of finding a foundation on which all mathematical truths could be proven. But in 1931 logician Kurt Gödel, aged just 25 at the time, dashed their hopes. He proved that there are inevitably unprovable statements in mathematics—statements that can neither be proven nor disproven. Initially, experts hoped this was an abstract result with no significant applications. But they were wrong.

Mathematicians now know of many unprovable problems. One of the first examples is the halting problem, which deals with the execution of algorithms. In the 1930s Alan Turing figured out that there is no algorithm that can predict whether a computer program with certain inputs will run forever or will stop at some point. At the time, Turing was working on the theoretical model of such a computer, now called the Turing machine. This theoretical machine consists of an infinitely long tape labeled with 1’s and 0’s and a head that reads the tape, describes it, and shifts it to the right or left. Such a machine can theoretically perform any kind of calculation—just like a computer.

Suppose you want to program a Turing machine to multiply two numbers. The 1’s and 0’s on the tape then correspond to the two numbers. Before the calculation, you define a certain number of states, or rules, for the machine, such as A, B, C, and D, as well as HALT. These states determine how the Turing machine acts with each input. For example: If the five-state machine reads a 1 on the tape in state A, it overwrites this with a 0, moves the tape to the left, and switches to state C. Two instructions are therefore required for each of the states A to D, depending on whether the machine finds a 1 or a 0 on the tape. Under certain circumstances (for example, state B when reading a 1), the machine can switch to the HALT state. In this case, the Turing machine stops, and the calculation is complete. The result would then be the numbers on the tape at that point.

As Turing proved, there is no Turing machine that can determine, for all possible configurations of Turing machines, meaning all algorithms, whether they will stop at some point. And this is where the industrious beavers come into play.

The Halting Problem

In the “busy beaver game,” developed in 1962, Hungarian mathematician Tibor Radó searched for the most diligent Turing machine of a certain size: What is the maximum number of calculation steps that a Turing machine with n states, which comes to a halt at some point, can perform?

.

.

.

Click the link below for the article:

.

__________________________________________