# Tag Info

Accepted

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

The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of $\Theta(\mathit{BB}(n))$, or indeed $\Omega(\mathit{BB}(n))$. Indeed, such an ...
• 278k

### Goldbach Conjecture and Busy Beaver numbers?

The statement is about infinitely many numbers, but its demonstration (or refutation) would have to be a finite exercise. If possible. The surprise may come from the (false) assumption that finding ...
• 3,276

### Goldbach Conjecture and Busy Beaver numbers?

The idea from the author was that you can write a program in 100 lines (any fixed finite number here) which does the following: takes number x, tests conjecture. If not true then stop else continue on ...
• 1,096

### Goldbach Conjecture and Busy Beaver numbers?

Aaronson has recently expanded in detail on this musing/ idea here working with Yedidia.[1] they find an explicit 4888 state machine for the Goldbachs conjecture. you can read the paper to see how it ...
• 11k

### Uncomputability of Busy Beaver Function

Here's a simple proof of the non-computability of the Busy Beaver function: Assume BB is computable. Then we can build a program that accepts a TM specification M and input x. Compute n = BB(|M|), ...
• 2,230

### Understanding proof for Busy Beaver being uncomputable

Just for the completeness, I will present my proof that shows uncomputability of BB function. The structure of a correct proof would look something like the following. Construct a universal Turing ...
• 221
Accepted

### Busy Beaver problem - Proof by contradiction

I know it took me a few reads before a grasped what it was saying, so maybe if we build $Q$ in a different and (much) more verbose way, it'll help. So let's start by assuming a Turing machine $\Sigma$...
• 176

### Computation of busy beaver function

Scott Aaronson discusses this here. He and his co-author find an explicit upper bound on $n$ for which $S(n)$ can be computed.
• 271
Accepted

### How far out can one determine a program is halting?

What you are describing is indistinguishable from: making a (free) copy of the Turing machine (in its current state) running it for $n$ steps seeing if it halted. I fail to see how this gives you ...
• 991

### Wanted: Concrete Example of Busy Beaver Holdout

Skelet has 43 holdouts (those with type = ----). At least No. 827123 (the very first in the lists) is still open, afaik. My "feeling" is that all but 6 (no idea, which!) have been shown to ...
• 77
Accepted

• 13.4k
1 vote

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

Use the same proof as RadÃ³ did in his paper: Assume there is a program $\Sigma$ that computes the value asked for, combine with a program that given $n$ computes $2 n$, and add $1$ to the result. Call ...
• 14.1k
1 vote

• 651
1 vote

### Small Turing machine accepting single complicated input?

Here is an algorithm that can be implemented with a Turing machine using a small number of states, and that only accepts inputs that I suspect are likely to look complicated to most humans. Let the ...
• 161k
1 vote
Accepted

### Is there a difference between extremely slow growing functions and constants with respect to computable functions?

Your definition of $f$ is $$f(n) > k \Longleftrightarrow B(k) \leq n.$$ Now suppose that $M$ is a Turing machine that runs in time $C n^{f(n)}$ but not in polynomial time. Since $M$ does not run ...
• 278k
1 vote
Accepted

### Are the outcomes of the maximum shifts function fixed regardless of our choice of axiomatic system?

Interesting but slightly confusing thoughts, indeed. Let us tread water slowly and cautiously. Suppose $\mathsf{ZF}$ is inconsistent. Suppose we continue to use $\mathsf{ZF}$. Every proposition ...
• 39.1k
1 vote

### Goldbach Conjecture and Busy Beaver numbers?

The Goldbach conjecture can be falsified (if actually false) by such a TM program; it can not be proven correct in this way (an insightful mathematician, however, might do this). Knowing BB(27) would ...
• 77

Only top scored, non community-wiki answers of a minimum length are eligible