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.

31 questions
Filter by
Sorted by
Tagged with
17 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)...
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 ...
1 vote
31 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 ...
44 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 ...
1 vote
62 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 ...
254 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' ...
31 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 ...
80 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(...
45 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 ...
31 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 ...
125 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 ...
1 vote
74 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, ...
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. ...
1 vote
36 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 {\...
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 ...
1 vote
69 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 ...
91 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: ...
1k views

1 vote
311 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 ...