Skip to main content
37 votes
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 ...
Yuval Filmus's user avatar
11 votes

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 ...
André Souza Lemos's user avatar
9 votes

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 ...
Eugene's user avatar
  • 1,096
8 votes

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 ...
vzn's user avatar
  • 11k
4 votes

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|), ...
gardenhead's user avatar
  • 2,230
4 votes

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 ...
James Parker's user avatar
4 votes
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$...
Lawtonfogle's user avatar
4 votes

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.
PeteyPabPro's user avatar
4 votes
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 ...
DirkT's user avatar
  • 991
3 votes

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 ...
Michael's user avatar
  • 77
3 votes
Accepted

Uncomputability of Busy Beaver Function

How do you know that $ M' = \langle Create_{n0} \mid Double \mid EvalS \mid Clean \rangle$ has N states? By definition $n_0$ is the size of the machine $M = \langle Double \mid EvalS \mid Clean \...
Vor's user avatar
  • 12.6k
3 votes
Accepted

Busy Beaver machines on semi-infinite tape

We look to the first approach in this answer. Let us denote this new function by $\Sigma_{\mathrm{semi}}(n)$. Also, call the function of the second approach $\Sigma_{\mathrm{bounce}}(n)$. Also, ...
wythagoras's user avatar
3 votes

Understanding proof for Busy Beaver being uncomputable

The reference blog has changed and it seems to have been corrected which includes the OP's correction. Although the waybackmachine archived this blog old uncorrected version (2013 version) but it can'...
An5Drama's user avatar
  • 203
3 votes
Accepted

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

If I recall correctly it started with $n = 64$, then $n = 25$ shortly after that with $n=23$, $n = 22$ and now $n = 19$.
Evil's user avatar
  • 9,465
2 votes

Is this padded version of the Halting Problem in NP?

Unless you're talking about promise problems, you are required to handle arbitrary inputs. Given a string $x\in\left\{0,1\right\}^*$, we have $x\in L$ iff $x=\langle M\rangle \cdot BB\left(|M|\right)...
Ariel's user avatar
  • 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 ...
vonbrand's user avatar
  • 14.1k
1 vote

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

If you look at the Wikipedia page for the Busy Beaver game (https://en.wikipedia.org/wiki/Busy_beaver) there is a section about "Maximum Shifts Function" which seems to answer your question.
NaturalLogZ's user avatar
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 ...
D.W.'s user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
John L.'s user avatar
  • 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 ...
Michael's user avatar
  • 77

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