Talk:Busy beaver

wvbailey

wvbailey's example should go on the main page. The main page currently makes no sense to anyone who doesn't already understand the subject. His explanation and example was entirely understandable and at least allowed me to understand what was being described in the main article. Thanks for that wvbailey!

Requirement of exact number of steps

The article mentions that "a statement of the exact number of steps it takes to reach the Halt state" is necessary because without it "the problem of verifying every potential entry is undecidable", citing the halting problem. However, doesn't the halting problem is that of determining halting of an arbitrary machine on ARBITRARY INPUT, and the latter requirement is key to the proof?

If there is a generalization of the halting theorem that prohibits creating an algorithm that for one specific input would predict whether an arbitrary machine would stop, such a generalization should definitely be mentioned on the corresponding "halting problem" page, and the current article should link specifically to that generalization. Otherwise the current article needs to reflect that the "exact number of steps" is only required because we don't know an algorithm to check, and do not even know WHETHER such an algorithm could exist. — Preceding unsigned comment added by 104.53.222.39 (talk) 01:37, 2 June 2020 (UTC)

I think the halting problem for any arbitrary input can be reduced to the halting problem for a blank-tape input (or any other specific input) by just taking your arbitrary-input machine, and turning into a larger blank-tape machine that just writes the input on the tape before starting. So solving the halting problem for the blank-tape machines solves it for all of them. Mrfoogles (talk) 22:55, 17 July 2024 (UTC)

Σ(17) > Graham's number and other comparisons

It has been shown, that Σ(17) > Graham's number.

What kind of Σ(n) would be about as big as TREE(3), SSCG(3), SCG(13), Loader's number, Rayo's number and Fish number 7? — Preceding unsigned comment added by 84.151.253.231 (talk • contribs)

Did Σ(n) and S(n) become computable?

Carbrickscity's reason, why Rayo's number is uncomputable: “No one will ever define a number with a googol symbols.”

Using the latest bounds, it can be determined, that Rayo(7339) > S(2⁶⁵⁵³⁶ - 1).

Only 7340 symbols in the first-order set theory and already 2⁶⁵⁵³⁶ - 1 states in the maximum shifts function, so I guess, Σ(n) and S(n) became computable. Also, Rayo(n) became 84.154.72.51's idea for TREE(3) in symbols.

The first-order set theory only needs a few thousand symbols for TREE(3). So, if we use the first-order set theory for TREE(3) in symbols, we can find out the actual exact value of TREE(3). 84.154.65.218 (talk) 09:43, 10 February 2023 (UTC)

The bound on Rayo(7339) is found by defining what the maximum shift function is in FOST, as well as the number 2^65536 - 1. In other words this in no way proves it computable, because you've just rewritten the same definition in a different language. 86.3.78.253 (talk) 07:34, 14 September 2023 (UTC)

"Computable" is a property of a function, and a computable function is one which is computed by some Turing machine. "Uncomputable number" is an unfortunate piece of terminology which seems to have originated from the site Googology Wiki, it is unfortunate since computability/uncomputability is a property of a function, not a number. It is easy to prove by contradiction that the busy beaver function cannot be a computable function (if you assume for a contradiction that it were computable, the halting problem would be solvable by running an n-state Turing machine for BB(n) steps, returning "halt" if it halted by that point, and "non-halt" if it did not.)

Numbers outputted form uncomputable functions are not necessarily larger than numbers outputted from computable functions either, which is another reason that "uncomputable number" vs. "computable number" are not good pieces of terminology for cataloguing large numbers. In fact there are uncomputable functions which are eventually dominated by computable ones, for example if f(x) is "0 if the xth Turing machine halts and 1 otherwise", and g(x) = x^2, then g, a comptuable function, eventually dominates f, an uncomputable function. C7XWiki (talk) 04:13, 11 April 2024 (UTC)

Proposal: Change of notation

What this article calls Σ(N) (aka "Rado's sigma function") seems to be called BB(N) in many sources: see for example [1], [2], [3], [4]. "BB" seems to be easier to remember than "Σ"; if I'm right that they are the same thing, I propose we change the usage here to replace it. — The Anome (talk) 20:54, 19 October 2023 (UTC)

Multiple of those sources you listed use S(n) as BB(n), not Σ(n). I think we should use BB for S(n), not the other way around, if we had to pick, but I'm not sure there is overall agreement on what BB(n) means. Mrfoogles (talk) 18:56, 3 July 2024 (UTC)

3 State 4 symbol Busy Beaver

https://www.sligocki.com//2024/05/22/bb-3-4-a14.html

describes a Busy Beaver candidate which puts more than Ackermann(14) symbols on the tape, in fact exactly $(2\uparrow ^{15}5)+14$ non-zero symbols on the tape NadVolum (talk) 11:41, 31 May 2024 (UTC)

New results

BB(5) = 47,176,870. [5] --jpgordon^{𝄢𝄆𝄐𝄇} 18:28, 2 July 2024 (UTC)

I've put that in but not sure the Σ(5) value isn't higher for some other one. NadVolum (talk) 19:48, 2 July 2024 (UTC)

I also took out the >= sign in the BB(2,4) case as it is now known that is the busy beaver value. A higher value of BB(2,5) is know but I don't believe any more values will ever be proven to be the busy beaver value. They all have cases which probably don't stop but we can't prove that because that would involve solving a hard problem like the Collatz one. NadVolum (talk) 23:42, 2 July 2024 (UTC)

Article technicality improvement

I think it's important to:

1. Reword the weasel 'disambiguation-like' language'.
2. Clearly explain how a busy-beaver program works sooner rather than later

Hence, for review:

The busy beaver game is a theoretical computer science problem to find a terminating program with a given sophistication that produces the most output (writing into the 'memory) possible.

On each move in the program, the current position is read and, combined with the current program state, produces what to write to the current position (the current value can be overwritten by itself) and which program state to run next.

Since an endlessly looping program producing infinite output or running for infinite time is easily conceived, such programs are excluded from the game.

The problem can also phrased as finding the machine that runs for the longest time - both games are similarly difficult.

The busy beavers are implemented as a halting Turing machine with an alphabet of {0,1} which writes the most 1s on the tape, using only a given set of states. As such the rules for the 2-state game are as follows:

• the machine must have at most two states in addition to the halting state, and
• the tape initially contains 0s only.

Creating an attempt for the longest busy beaver game means conceiving a transition table aiming for the longest output of 1s on the tape while making sure the machine will halt eventually.

An nth busy beaver, BB-n or simply "busy beaver" is a Turing machine that wins the n-state busy beaver game. That is, it attains the largest number of 1s among all other possible n-state competing Turing machines. The BB-2 Turing machine, for instance, achieves four 1s in six steps.

Calculating the longest possible valid number of moves for more than a few states is incredibly time-consuming. Recent work has found the value for BB-5 - 47,176,870 moves.

Deciding the number of 1s, or the running time, of any size Busy Beaver is incomputable. This has implications in computability theory, the halting problem, and complexity theory. The concept was first introduced by Tibor Radó in his 1962 paper, "On Non-Computable Functions"

2A00:23C8:CA00:3C01:2D8E:90F5:70D1:1973 (talk) 21:30, 2 July 2024 (UTC)

I don't know that we're going to do better than what's in the recent article about BB(5):

Turing machines perform computations by reading and writing 0s and 1s on an infinite tape divided into square cells, using a “head” that operates on one cell at a time. Every machine has a unique set of rules that governs its behavior.

Each of these rules specifies what the head should do when it moves into a new cell, depending on whether it encounters a 0 or a 1 already there. This means a Turing machine’s instructions can be summarized in a table with one row for each rule and two columns (one for when the head encounters a 0 and the other for when it encounters a 1). One rule might be, “If you read a 0, replace it with a 1, move one step to the right, and consult rule C,” in the first column, and “if you read a 1, leave it unchanged, move one step to the left, and consult rule A,” in the second. This is what all the rules look like, except for one special rule that tells the machine when to stop running.

Of course, we can't plagiarize this, but I think we could quote it, or rephrase it. In particular, giving concrete examples of specific rules instead of just abstractly describing a function of two inputs and three outputs will be more easily understandable to the layperson. Anyway, it's a place to start. Mr. Swordfish (talk) 21:53, 2 July 2024 (UTC)

Suggest adding the following Example, with surrounding text from the article included for context:

The n-state busy beaver game (or BB-n game), introduced in Tibor Radó's 1962 paper, involves a class of Turing machines, each member of which is required to meet the following design specifications:

• The machine has n "operational" states plus a Halt state, where n is a positive integer, and one of the n states is distinguished as the starting state. (Typically, the states are labelled by 1, 2, ..., n, with state 1 as the starting state, or by A, B, C, ..., with state A as the starting state.)
• The machine uses a single two-way infinite (or unbounded) tape.
• The tape alphabet is {0, 1}, with 0 serving as the blank symbol.
• The machine's transition function takes two inputs:

1. the current non-Halt state,
2. the symbol in the current tape cell,

and produces three outputs:

1. a symbol to write over the symbol in the current tape cell (it may be the same symbol as the symbol overwritten),
2. a direction to move (left or right; that is, shift to the tape cell one place to the left or right of the current cell), and
3. a state to transition into (which may be the Halt state).

Example

The rules for state 1 might be:

If the current symbol is 0, write a 1, move one space to the left, and transition to state 2.

If the current symbol is 1, write a 0, move one space to the right, and transition to state 3.

There are thus (4n + 4)²ⁿ n-state Turing machines meeting this definition because the general form of the formula is (symbols × directions × (states + 1))^{(symbols × states)}.

The transition function may be seen as a finite table of 5-tuples, each of the form

(current state, current symbol, symbol to write, direction of shift, next state).

Mr. Swordfish (talk) 16:58, 3 July 2024 (UTC)

I did not realize this had just been added and have just cut down the section a bit: it's very helpful to have a clear definition but the large amount of detail was a bit intimidating, even though it was simplified (transition functions are a bit non-elementary). Hopefully this should give a clear definition without stopping people from scrolling past it if necessary (though of course the rest of the article is even more technical). Mrfoogles (talk) 18:53, 3 July 2024 (UTC)

What do you think about adding the Example as above? My experience teaching math to non-mathematicians is that a concrete example goes a long way towards explaining an abstract definition. Mr. Swordfish (talk) 19:57, 3 July 2024 (UTC)

I think that's a good idea, but maybe with a complete machine? Having just the first state is helpful, but I think it would be better to have a full machine, maybe with a short summary of what it does. The only problem is we don't want to divert too long from Busy Beavers to Turing machines, and the section is pretty long already. A 1-state Turing machine would be quicker to write (only 2 lines, in comparison for 4 needed for a 2-state Turing machine), but wouldn't illustrate the changing of the states.

It would be fun to have one of the busy beavers as an example, but the 1-state is probably too simple and the 2-state overly complicated.

Maybe:

Example

The rules for a 1-state Turing machine might be:

• In state 1, if the current symbol is 0, write a 1, move one space to the right, and transition to state 1
• In state 1, if the current symbol is 1, write a 0, move one space to the right, and transition to HALT

This Turing machine would move to the right, swapping the value of all the bits it passes. Since the starting tape is all 0s, it would make an unending string of ones. This machine would not be a busy beaver contender because it runs forever on a blank tape. A machine with more states might transition to a state with different behaviour, rather than halting, when it hits a 1. Mrfoogles (talk) 19:01, 4 July 2024 (UTC)

I think a complete machine makes it more concrete, and you can also summarize it, so people try to see the behaviour in the machine, rather than having to try to deduce it from the source code. Mrfoogles (talk) 19:02, 4 July 2024 (UTC)

Better source needed for table of results

Currently, there is no source for all of the more-than-2-symbol results. It's unclear if such a source even exists: probably someone keeps and index somewhere, but it's unlikely to exist in a non-self-published source. Should we just cite blogs? Or should the rest of the table be deleted? Mrfoogles (talk) 21:19, 4 July 2024 (UTC)

Also, should the technical tag be removed? Mrfoogles (talk) 22:12, 5 July 2024 (UTC)

S(5) Solved

The following article claims that S(5) has been solved.

Amateur Mathematicians Find Fifth ‘Busy Beaver’ Turing Machine | Quanta Magazine BAbdulBaki (talk) 12:36, 6 July 2024 (UTC)

It has been. It should be in the article: I know it is in some places. If the article claims it's not, it should be updated. Mrfoogles (talk) 08:01, 8 July 2024 (UTC)

"uncomputability" - "counterexplanation" retry with an improved description

previous attempt: https://en.wikipedia.org/w/index.php?title=Talk%3ABusy_beaver&diff=1138560813&oldid=1112203473

There are 2 new functions.: num(n) and space(n)

So, here is an improved description, why num(n), Σ(n), space(n) and S(n) could have become computable.

In How big is Rayo's Number 拉約數, Carbrickscity showed and said the hurdles, why Rayo's number is uncomputable.

Rayo(n) is defined as: "the smallest natural number greater than all natural numbers named by an expression in the language of first-order set theory with n symbols or less". This means, the smallest number, that requires at least n + 1 symbols in the first-order set theory.

Rayo's number is Rayo(10¹⁰⁰). In the brackets, you can see the hurdles.

No one will ever define a number with 10¹⁰⁰ symbols.

number of seconds since the big bang ≈ 10¹⁷ seconds

Planck time ≈ 10^-44 seconds

number of Planck times since the big bang ≈ 10⁶¹ < 10¹⁰⁰

number of atoms/particles in the observable universe ≈ 10⁸⁰ < 10¹⁰⁰

But, one of the lower bounds for one of the smaller Rayo(n) values looks like, num(n), Σ(n), space(n) and S(n) could have become computable.

Emk has shown, that Rayo(7901) > S(2⁶⁵⁵³⁶ - 1), where S(n) is the maximum shifts function.

2⁶⁵⁵³⁶ - 1 states in the maximum shifts function is a lot of states and it only took 7902 symbols in the first-order set theory. Because 7902 symbols can easily be written down, it looks like, Emk could have disproven the uncomputability of num(n), Σ(n), space(n) and S(n) with his Rayo(7901) > S(2⁶⁵⁵³⁶ - 1). And, this is not even the latest bound.

Using the latest bounds, it can be determined, that Rayo(7339) > S(2⁶⁵⁵³⁶ - 1).

2⁶⁵⁵³⁶ - 1 states in the maximum shifts function is a lot of states and it only took 7340 symbols in the first-order set theory. Because 7340 symbols can easily be written down, I guess, num(n), Σ(n), space(n) and S(n) became computable.

Also, where is the exact value of TREE(3)? With a strong symbol function, like the first-order set theory, Rayo(n), it should be possible to find out the exact value of TREE(3). The previous symbol function used for TREE(3) was strictly finite mathematics, but it takes 2↑↑1000 symbols for TREE(3). The first-order set theory, Rayo(n), is a much stronger symbol function than strictly finite mathematics. Since Rayo(7339) > S(2⁶⁵⁵³⁶ - 1), S(n) ≥ space(n) ≥ Σ(n), Σ(2000) ≥ Loader's number, 2⁶⁵⁵³⁶ - 1 >> 2000 and Loader's number >> SCG(13) > SSCG(3) >> TREE^TREE(3)(3), the first-order set theory, Rayo(n), would reduce the number of symbols for TREE(3) from 2↑↑1000 to a few thousands. So, if we use the first-order set theory, Rayo(n), for TREE(3) in symbols, we can find out the actual exact value of TREE(3). 94.31.89.138 (talk) 11:53, 5 October 2024 (UTC)

The problem here is that you’ve shown that Rayo(x) is bigger than S(y), but there are two problems. First, Rayo(x) is also uncomputable; you’ve just reduced uncomputability to uncomputability. Second, to make a function computable, you can’t just upper-bound a single value (e.g. I could say that S(5) < the constant function 100 million evaluated at 5), but that does not allow me to upper bound the S(n) function in general. So this does not place an upper bound on S(n), and even if it did it would be useless because Rayo(n) is uncomputable, as well as because S(n) can be (not even with too much difficulty) proven to be impossible to compute in general anyways, so a computable upper bound has been proven to not exist. Mrfoogles (talk) 15:18, 5 October 2024 (UTC)

Also, just because Rayo(7339) > TREE^{TREE(3)}(3) doesn't mean you can calculate the exact value of Tree(3); for example just because I know someone is under the age of 200 doesn't mean I know exactly what age they are. Not that we can calculate Rayo(7339) to the best of my knowledge anyways. It is neat that Rayo(7339) > S(2^65536 - 1), though. Mrfoogles (talk) 16:32, 5 October 2024 (UTC)