# Questions tagged [busy-beaver]

The Busy Beaver problem is about finding the sequence of n-state Turing Machines writing the most 1's on a tape.

31 questions
Filter by
Sorted by
Tagged with
2k views

### Goldbach Conjecture and Busy Beaver numbers?

Background: I am a complete layman in computer science. I was reading about Busy Beaver numbers here, and I found the following passage: Humanity may never know the value of BB(6) for certain, let ...
• 317
998 views

### Computation of busy beaver function

The busy beaver max shifts function, $S(n)$, has known values for $n\leq4$. Is there some basic, structural reason why it's inconceivable that we will ever find $S(n)$ for $n>4$? What is so ...
• 271
3k views

### Are there any functions with Big O (Busy Beaver(n))?

So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than ...
• 211
254 views

### Wanted: Concrete Example of Busy Beaver Holdout

I understand from the Wikipedia page on the Busy Beaver problem that the Busy Beaver values for 5-state 2-symbol (quintuple) Turing-machines have not been determined, because there are 'holdout' ...
• 243
1k views

### Is a secondary TM sufficient to detect all loops?

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever ...
• 339
124 views

### Busy Beaver machines on semi-infinite tape

The Busy Beaver problem is to find the largest number of non-blank characters that are printed by a terminating Turing machine of no more than a given size on the blank input. The usual Busy Beaver ...
• 12.6k
70 views

### What is the minimum acceleration of a macro machine?

In the context of Turing machines, consider a $k$-sized macro machine (k-MM) which operates on groups of $k$ symbols at once. This is a common optimization in the search for Busy Beavers, explained e....
• 339
370 views

### What is the smallest $n$ such that $BB(n) >$Graham's number?

BB represents the busy beaver function here. Do we even have any idea of what order of magnitude $n$ would have? Is it possibly around 10, or more like 1000?
• 317
11k views

### Understanding proof for Busy Beaver being uncomputable

I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold. (BB(n) is defined as the number of steps ...
• 185
1k views

### Uncomputability of Busy Beaver Function

https://en.wikipedia.org/wiki/Busy_beaver#Proof_for_uncomputability_of_S.28n.29_and_.CE.A3.28n.29 So this is wikipedia's proof of why Busy Beaver Function is uncomputable. But I don't get two things. ...
• 215
1k views

• 269
166 views

### What is the simplest way to understand Turing machines and the busy beaver problem? [closed]

The Wikipedia description has way too much math.
• 147
31 views

### Is the Busy Beaver with n states also the busiest Turing machine (counted in steps) with n states?

Based on the Busy Beaver rules (2 letter alphabet, 2-way unbounded tape, program must halt, etc) I was wondering if the Busy Beaver for each n is also the program that does the most steps, or if there ...
• 101
45 views

### Small Turing machine accepting single complicated input?

This imprecise question is about a simple example for the following problem. I would like a Turing machine with few states that accepts only inputs which look complicated to the naked eye. Of course ...
• 265
91 views

### Busy-Beaver-like question for WHILE-Programs (Theoretical CS)

So this is exam-task is called "Busy WHILE-Programs" In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following: ...
17 views

### Short SK combinator expression with long reduction / Busy Beaver for SK combinators

Question (short and simple version): Can anyone suggest a very short SK combinator expression with a ridiculously long, but still terminating, reduction path (ignoring loops)? Question (longer version)...
• 111
44 views

### How do people working on the Busy Beaver function keep track of all the turing machines?

I'm a CS undergrad so forgive me if this question isn't formulated well. I got curious about the Busy Beaver function recently, and it got me wondering how all the n-state Turing machines are kept ...
• 101
80 views

### Busy Beaver non-computability proof by contradiction

When proving the non-computability of the Busy Beaver function by contradiction, people create machines that are able to calculate the Busy Beaver function, BB(n), and also write more than 1s than BB(...
• 101