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.
19
questions
0
votes
0answers
2 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:
...
0
votes
0answers
15 views
building turing machine for busy beaverproblem
I have tried to build a turing machine for busy beaver problem that has BB(2,3) two variables and three variables but i am not sure if its correct or it needs any changes
1
vote
0answers
44 views
What do we know about the reciprocal busy beaver series? [closed]
[Cross-posted from Math SE - apologies if this is not appropriate.]
I just read these excellent lecture notes by Scott Aaronson, and I found the second homework problem at the end to be incredibly ...
4
votes
0answers
93 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' ...
0
votes
0answers
127 views
Busy Beaver Instruction Generator and Computablity
Question 1
From busy beaver uncomputablity it follows that we cannot design algorithm that for every input N, generate the appropriate set of TM instructions (the bit value of every bit in every card)...
3
votes
2answers
536 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.
...
4
votes
1answer
132 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?
1
vote
1answer
90 views
Is this padded version of the Halting Problem in NP?
I'm using the following definition of $NP$:
$$A \in NP \Longleftrightarrow A(x) = \exists w: B(x,w) $$
where $B \in P$ and $|w| = poly(|x|)$.
Now instead of the problem whether the program $\Pi$ ...
12
votes
5answers
926 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 ...
6
votes
0answers
52 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....
6
votes
1answer
76 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 ...
1
vote
0answers
89 views
Busy beaver construction system [closed]
I want to construct a busy beaver TM which has the alphabet $\Sigma = \{1,2, X\}$ and $X$ is the blank symbol. I want to do this using 3, 4 and 5 states (means one just for halting, so 3 states = 2 '...
2
votes
3answers
4k 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 ...
4
votes
1answer
473 views
Busy Beaver problem - Proof by contradiction
I am trying to understand a proof regarding the Busy Beaver problem that uses a proof by contradiction approach to show $\sum(n)$ is Turing-uncomputable:
Find $\sum(n) = max \{\sum(M) | M \in M(n) \...
6
votes
1answer
498 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 ...
1
vote
1answer
192 views
Why can't we detect infinite loops in the busy beaver problem?
I was reading about the busy beaver problem the other day and I'm confused as to why we can't keep an array of Turing machine states that the machine has been through and simply iterate through it at ...
0
votes
1answer
101 views
What is the simplest way to understand Turing machines and the busy beaver problem? [closed]
The Wikipedia description has way too much math.
13
votes
3answers
499 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 ...
3
votes
1answer
98 views
Given an n-state TM, can we construct an m-state TM (m>n) to determine if it halts?
BB(n) is roughly the maximum number of new states an n-state TM can run into without halting. So for a particular n, if we know BB(n), then we can find out if an arbitrary n-state TM halts by running ...
