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.
33 questions
0
votes
1
answer
84
views
Reduce $A_{TM}$ to Busy Beaver
I have a question described as follows from the Sipser's TOC textbook:
Let $\Gamma=\{0,1, \sqcup\}$ be the tape for all TMs in this problem. Define the busy beaver function $BB: N \rightarrow N$ as ...
- 7
0
votes
0
answers
67
views
How many states does a 2-symbol turing machine need on average to compute a N bit number?
The busy beaver problem asks what is the largest number computable by a 2-symbol N-state Turing machine, however, most numbers however are not re-presentable by a smaller program.
For a sufficiently ...
5
votes
1
answer
69
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)...
- 171
1
vote
0
answers
35
views
Hardwiring advice (bit string) into Turing machine
In paper, page 5, 1st paragraph, it is stated that:
Notice that an n-state Busy Beaver, if we had it, would serve as an O(n log n)-bit advice string, “unlocking” the answers to the halting problem ...
- 11
0
votes
0
answers
57
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
1
vote
1
answer
74
views
How far out can one determine a program is halting?
Suppose we have a finite set of programs, say, something like every Turing machine with 2 states and 7 symbols. After running all of them for a very long time, we've narrowed it down to a small subset ...
- 306
0
votes
1
answer
34
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
0
votes
0
answers
106
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
-1
votes
1
answer
49
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 ...
- 261
0
votes
0
answers
33
views
What is BB(n) terminology precisely saying about symbols, states, space, and steps involved?
This question is mainly about the clarification of the terminology BB(n), not how busy beavers work. It seems common to refer to busy beaver numbers like ...
- 162
2
votes
1
answer
134
views
Is there a difference between extremely slow growing functions and constants with respect to computable functions?
So let's say we have the function $f(n)$ that gives $k$ such that $k$ is the smallest number that gives a busy beaver function $B$ value from input $k$ that is greater than $n$. Or more succinctly the ...
- 217
1
vote
1
answer
79
views
Are the outcomes of the maximum shifts function fixed regardless of our choice of axiomatic system?
It is known that there is a $748$-state Turing machine that halts if and only if $\mathsf{ZF}$ is inconsistent. So by Gödel's second incompleteness, $\mathsf{ZF}$ cannot find what $S(748)$ exactly is, ...
- 387
1
vote
0
answers
37
views
What kind of small Turing machines evade current attempts to prove their halting?
On the german Wikipedia, I read that:
Der Bulgare Georgi Georgiev veröffentlichte 2003 eine Untersuchung, in
der er fleißige Biber daraufhin analysierte, ob sie anhalten würden
oder nicht.[2] Für {\...
- 480
10
votes
2
answers
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 ...
- 231
1
vote
0
answers
75
views
Can a second-order busy beaver function/turing machine be programmed?
I have seen a computer program at https://github.com/pkrumins/busy-beaver/blob/master/busy-beaver.py that computes Busy Beaver numbers (well, pretends to). It has busy beaver numbers up to 4, and I am ...
- 11
0
votes
2
answers
101
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:
...
1
vote
0
answers
89
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 ...
- 1,146
8
votes
1
answer
264
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
0
votes
0
answers
174
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)...
- 101
4
votes
2
answers
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
5
votes
1
answer
385
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
1
vote
1
answer
110
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$ ...
- 1,048
13
votes
5
answers
3k
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
6
votes
0
answers
75
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
6
votes
1
answer
135
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.7k
1
vote
0
answers
118
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 '...
- 269
4
votes
4
answers
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
4
votes
1
answer
1k
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) \...
- 249
6
votes
1
answer
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
1
vote
1
answer
320
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 ...
- 113
0
votes
1
answer
169
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
13
votes
3
answers
1k
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
3
votes
1
answer
173
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 ...
- 527