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.
37 questions
1
vote
0
answers
41
views
Is "Tiny Tag" Turing-Complete?
I have recently been investigating Turing-Complete systems and discovered something called “Cyclic Tag”. It is relatively simple to explain, it involves transforming an initial binary string through ...
- 11
2
votes
0
answers
106
views
Busy beaver with Turing Machine
Basic setups:
A Turing machine M operates on a doubly infinite tape. The tape is divided into cells. Each cell can hold either a 0 or a 1 (meaning, we will consider only TM’s with two symbols). The ...
- 97
1
vote
1
answer
112
views
Are these two definitions of the Busy Beaver numbers equivalent?
Let M be any n-state Turing Machine on an initially blank tape.
The n-th Busy Beaver number BB(n) has been defined by several authors since Radó as both (1) the largest number of steps M can take ...
- 113
1
vote
0
answers
86
views
Goldbach's conjecture and Meta Busy Beavers
I was wondering whether one could solve Goldbach's conjecture more efficiently by introducing meta busy beavers, which I define as busy beavers which call busy beavers.
This would only work if the ...
- 11
0
votes
1
answer
187
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
120
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 ...
- 166
5
votes
1
answer
146
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)...
- 173
1
vote
0
answers
56
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 ...
- 21
0
votes
0
answers
98
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
139
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 ...
- 316
0
votes
1
answer
65
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
167
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
82
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
68
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
208
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