Busy Beaver Function: Range of BB Sets

[SSequence]

I searched a bit before posting this question just in case to see if I was missing something obvious. I didn't see a direct or clear answer which I could easily understand/decipher. I feel that it is a fairly entertaining problem at any rate.

The question is really simple. Let bb:N→N denote the busy beaver function. Define the set:
BB = { bb(n) | n∈N }

Now it is known and (relatively) easy to show that the set BB is halt-reducible (and actually, conversely the halt-set is BB-reducible).

=====

But I was thinking, where does this set BB exactly fall -- and how do we prove it? For example if we define:
R = collection of recursive sets
RE = collection of r.e. sets
CRE = collection of co-r.e. sets
H = collection of halt-reducible sets

Then define:
A1 = R
A2 = RE - R
A3 = CRE - R
A4 = H - RE - CRE

Now one could show without too much difficulty that:
BB ∉ A1
BB ∈ H

With a little more work one can show that:
BB ∉ A2
That can be done by demonstrating that, in case the above statement is false, we can then obtain a recursive function f:N→N such that for all x:
f(x) ≥ bb(x)
... and hence a contradiction.

=====

Now my question is simple. We have two possibilities left:
(1) BB ∈ A3
(2) BB ∈ A4

Which of the above two is true?
Unless I have made a big mistake somewhere in formulating the question, it seems to me that the "falsity" (to establish the truth would seemingly require a direct construction) of first possibility can be demonstrated by "lack of existence" of certain "kind" of partial recursive functions**. I can't think of any example which demonstrates the existence of such partial recursive functions.

** By that I simply mean partial recursive functions with a certain property (which could be stated precisely without much difficulty). But first, let's see whether I have communicated the question in a good enough manner.

 

[Mark44]

I searched a bit before posting this question just in case to see if I was missing something obvious. I didn't see a direct or clear answer which I could easily understand/decipher. I feel that it is a fairly entertaining problem at any rate.

The question is really simple. Let bb:N→N denote the busy beaver function. Define the set:
BB = { bb(n) | n∈N }

How does this define anything? What does bb(n) mean? Also, I'm not familiar with the busy beaver function.

Now it is known and (relatively) easy to show that the set BB is halt-reducible (and actually, conversely the halt-set is BB-reducible).

=====

But I was thinking, where does this set BB exactly fall -- and how do we prove it? For example if we define:
R = collection of recursive sets
RE = collection of r.e. sets
CRE = collection of co-r.e. sets
H = collection of halt-reducible sets

Then define:
A1 = R
A2 = RE - R
A3 = CRE - R
A4 = H - RE - CRE

Now one could show without too much difficulty that:
BB ∉ A1
BB ∈ H

With a little more work one can show that:
BB ∉ A2
That can be done by demonstrating that, in case the above statement is false, we can then obtain a recursive function f:N→N such that for all x:
f(x) ≥ bb(x)
... and hence a contradiction.

=====

Now my question is simple. We have two possibilities left:
(1) BB ∈ A3
(2) BB ∈ A4

Which of the above two is true?
Unless I have made a big mistake somewhere in formulating the question, it seems to me that the "truth" or "falsity" of first possibility can be demonstrated respectively by "existence" or "lack of existence" of certain "kind" of partial recursive functions**. I can't really think of any example which demonstrates the existence of such partial recursive functions.

** By that I simply mean partial recursive functions with a certain property (which could be stated precisely without much difficulty). But first, let's see whether I have communicated the question in a good enough manner.

 

[SSequence]

How does this define anything? What does bb(n) mean? Also, I'm not familiar with the busy beaver function.

Well if you search for it, you can find a lot of articles related to it.

You can also search for the original paper by Tibor Rado (which shouldn't be that difficult to read given that the topic in consideration is relatively easy to understand). However, since I haven't really read it, I can't say for sure.

If you meant that the notation isn't very clear, what I meant explicitly was:
BB = { bb(0), bb(1), bb(2), bb(3), bb(4),...}

At any rate, you could define it in the following manner for example:
Consider a programming language (whose variables have all the valid range of N={0,1,2,3,...}) with following commands to change variable values:
v=v+1 (increase by 1)
v=v-1 (decrease by 1) -- if v is 0 don't change the value

One thing here is that we DON'T allow any commands (or any similar commands) of the form:
v=constant
For example, a command like v=100 would be prohibited. That's because we want to have finite number of programs of any given length (that is, number of instructions).

Now you can add any reasonable control structure (and a condition type within the control structure) to such a language to make it powerful enough to compute any partial recursive function (goto, while, for ... anyone of these will suffice).
As one example of a very similar language one can search for "register machines".

Now using a specific computational model (register machines, turing machines etc.) one can define the function
bb : N→N as:
bb(x) = the largest number of steps a program of size/length x runs before it halts (given a blank tape or 0 input)

for example (hypothetically) suppose we had 10 programs of a given size(say 5). Then we just run all the programs on 0 input: Suppose the test results were as follows (for programs P1 to P10).
P1: runs forever on 0 input
P2: runs forever on 0 input
P3: runs for 100 steps before halting (on input=0)
P4: runs for 150 steps before halting (on input=0)
P5: runs forever on 0 input
P6: runs for 50 steps before halting (on input=0)
P7: runs for 25 steps before halting (on input=0)
P8: runs for 150 steps before halting (on input=0)
P9: runs for 5 steps before halting (on input=0)
P10: runs forever on 0 input

In the above case, we have bb(5)=150.

 

[Mark44]

How does this define anything? What does bb(n) mean?

Well if you search for it, you can find a lot of articles related to it.

I shouldn't have to search for it -- you're the one with the question, so you should provide at least minimal definitions of what your question is about.

If you meant that the notation isn't very clear, what I meant explicitly was:
BB = { bb(0), bb(1), bb(2), bb(3), bb(4),...}

Which gets me no closer to understanding what this set contains.

 

[TeethWhitener]

Which gets me no closer to understanding what this set contains.

you can define the function bb : N→N as:
bb(x) = the largest number of steps a program of size/length x runs before it halts (given a blank tape or 0 input)

Figuring out whether bb(n) is in co-RE is an interesting problem, but on this forum you might be better off asking a mentor to migrate this thread to the "Set theory, logic, and probability" subforum. That seems to be where the complexity theory folks hang out.

 

[Mark44]

on this forum you might be better off asking a mentor to migrate this thread to the "Set theory, logic, and probability" subforum.

That was my thought as well -- thread is moved.

 

[Deedlit]

BB is recursively enumerable, I think. (Halt is the classic example of a recursively enumerable set.)

 

[SSequence]

I am not quite sure that is true. Perhaps you might have something else in mind (some other set or some other technique).

Here is the relevant part from my original post:

...
With a little more work one can show that:
BB ∉ A2
That can be done by demonstrating that, in case the above statement is false, we can then obtain a recursive function f:N→N such that for all x:
f(x) ≥ bb(x)
... and hence a contradiction.

...

Basically A2 can be replaced with (A1∪A2)=RE.

Perhaps a little bit of elaboration would make it clearer. If a set is r.e. then obviously there should exist some total recursive function (one variable) whose range is equal to that set.

Now suppose BB is r.e. and g:N→N is just such a function for the set BB. We could obtain the function f (described in the quote) in the following way:
Start from value 0 and in increments of 1 keep outputting the value of function g. Ignore repeats and smaller values (don't increase counter). Each time a greater value occurs (than current one), increase counter by 1. When counter equals the input, output the corresponding current value.

I know it is a little vague to describe it in words. An example should probably make it clearer. As a (hypothetical) example suppose we had:
g(0)=10, g(1)=15, g(2)=15, g(3)=5, g(4)=10, g(5)=25, g(6)=40, g(7)=30, g(8)=35, g(9)=45, g(10)=50
In that case the first few values of f would be:
f(0)=10, f(1)=15, f(2)=25, f(3)=40, f(4)=45, f(5)=50

 

[Deedlit]

Hmm, that makes sense. This is the argument I had in mind:

1. Halt is recursively enumerable (trivial)
2. Halt and BB are Turing equivalent (not hard to argue)
3. a set Turing equivalent to a recursively enumerable set is recursively enumerable

I thought that that last statement was true, especially since I have frequently seen reference to r.e. (or co-r.e.) Turing degrees, which would suggest that a Turing degree either had r.e. sets or non-r.e. sets. But perhaps that is not true.

If not, then perhaps a strategy for proving BB not co-r.e. would be to show that a set Turing equivalent to a nonrecursive r.e. set cannot be co-r.e.

EDIT: Eh, that strategy is probably no good since it looks like Turing degrees are closed under complement. So perhaps BB is co-r.e. after all.

 

[SSequence]

Note that below whenever I use the word reducibility, I mean turing reducibility (as, I think, there are also many other kind of reducibilities too).

To expand a bit on the points mentioned in the previous post:
If we have some set A and its complement as A' then it should be true that:
A' is A-reducible
A is A'-reducible

Now suppose we have the sets "Halt" and "BB". It is known that:
BB is Halt-reducible
Halt is BB-reducible
Because of the above I think the following is true too:
{ collection of all sets that are Halt-reducible } = { collection of all sets that are BB-reducible}

But we could also essentially take the complement of Halt (in place of Halt itself) and not much of the last paragraph would change.

Coming back to the question in OP:

EDIT: Eh, that strategy is probably no good since it looks like Turing degrees are closed under complement. So perhaps BB is co-r.e. after all.

To show that one would have to show a reasonable description of a partial recursive function (say f:N→N) such that:
f(x) terminates whenever x∉BB
f(x) runs forever whenever x∈BB

All the partial recursive functions I have seen till now are of a different kind than this --- in the following sense:
Suppose we are given partial recursive function F:N→N. Now suppose we have a total recursive function countF:N→N which "enumerates" the positions where the function f is undefined.

An example would probably make the relation between F and countF clearer compared to further descriptions:
F(0)=undefined, F(1)=1, F(2)=1, F(3)=undefined, F(4)=1, F(5)=1, F(6)=1, F(7)=undefined, F(8)=1, F(9)=undefined, F(10)=undefined
Then we have:
countF(0)=0, countF(1)=3, countF(2)=7, countF(3)=9, countF(4)=10, ...

Every example I have seen of a partial recursive function F, the corresponding function countF is always recursively bounded (the upper limit is given by some recursive function).

But here, if BB is supposed to be co-r.e. then we would need to give the example of just such a function (with the opposite property). If we want to show it isn't co-r.e., an elementary trick might be to suppose it is and then derive a contradiction. But, on the surface, such an elementary doesn't seem to work here (at least directly).

 

[stevendaryl]

$BB$ is co-re. Here's a sketch of an algorithm for enumerating the complement of $BB$:

Let's introduce a sequence of "approximations" to $bb(n)$ as follows:

• $bb_m(n) = 0$ if $n > m$
• Otherwise, $bb_m(n)$ is the largest value of $k$ such that $k \leq m$ and there is a program of size $n$ or less that halts in $k$ steps.

[Edit]: was $k \leq n$
Note that for each $m$, the function $bb_m(n)$ is perfectly computable. And $bb(n)$ is the "limit" of $bb_m(n)$ in the following sense: $bb(n) = lim_{m \rightarrow \infty} bb_m(n)$.

Now, if $bb_m(n+1) > bb_m(n)$, then that means that any number $k$ such that $bb_m(n) < k < bb_m(n+1)$ is definitely not equal to $bb(n')$ for any value of $n'$.

So we can generate all the elements of $\bar{BB}$, the complement of $BB$, by running through all possible values of $m$, and generating all $k$ such that $bb_m(n) < k < bb_m(n+1)$,

 

[Deedlit]

That's a great idea, but I don't think it quite works as is. $\lim_{m\rightarrow\infty}bb_m(n)$ is the largest value of $k$ such that $k \le n$ and there is a program of size $n$ or less that halts in $k$ steps. So for example $\lim_{m\rightarrow\infty}bb_m(n) \le n$.

We can use the definition

$bb_m(n)$ is the largest value of $k$ such that $k \le m$ and there is a program of size $n$ or less that halts in $k$ steps.

Then we will have $bb(n) = \lim_{m\rightarrow\infty}bb_m(n)$. The problem is that, while a $k$ such that $bb_m(n) < k < bb_m(n+1)$ will be less than $bb(n+1)$, I don't see any reason why it will not be equal to $bb(n')$ for some $n'$.

 

[SSequence]

$BB$ is co-re. Here's a sketch of an algorithm for enumerating the complement of $BB$:
...

I can't quite follow your argument "exactly" but here is what I understand of the basic idea.

What you are doing is using a function from N² to N whose basic property is such that the maximum number in its n-th row is well-defined (finite that is) and is equal to bb(n).

So basically because you are considering adjacent rows in your function, I think if its correct then one can either use induction or induction-like argument (probably the stronger version) to establish it (or possibly to see whether there are some issues). As I have understood, if the idea works correctly, then it will successfully enumerate all the points (bb(n),bb(n+1))** while it (gradually) sweeps through the rows n and n+1.
A potential problem that "might" exist here is to guarantee that none of the points from bb(0) to bb(n-1) will occur in this enumeration (while "sweeping" through between rows n and n+1). I am not quite confident about this either way, so I can't really say.

Nevertheless, the method is interesting enough at any rate.

** By that I mean the set of points { bb(n)+1, bb(n)+2, ..., bb(n+1)-2, bb(n+1)-1 }

 

[stevendaryl]

That's a great idea, but I don't think it quite works as is. $\lim_{m\rightarrow\infty}bb_m(n)$ is the largest value of $k$ such that $k \le n$ and there is a program of size $n$ or less that halts in $k$ steps. So for example $\lim_{m\rightarrow\infty}bb_m(n) \le n$.

That was a typo. I meant $k \leq m$. The idea is that to compute $bb_m(n)$, you just run programs for $m$ steps to see if they halt. If they don't halt in $m$ steps, then assume that they don't halt.

We can use the definition

$bb_m(n)$ is the largest value of $k$ such that $k \le m$ and there is a program of size $n$ or less that halts in $k$ steps.

Yes, that's what I meant.

Then we will have $bb(n) = \lim_{m\rightarrow\infty}bb_m(n)$. The problem is that, while a $k$ such that $bb_m(n) < k < bb_m(n+1)$ will be less than $bb(n+1)$, I don't see any reason why it will not be equal to $bb(n')$ for some $n'$.

First of all, $bb(n)$ is defined so that it's monotonically increasing: $bb(n+1) \geq bb(n)$. So if $bb(n') = k < bb(n+1)$, then that must mean that $n' < n+1$. That means that there is a program of size $n'$ that halts in $k$ steps. But we've already checked all programs of size less than $n$ for halting within $k$ steps. So we would already know that $bb_m(n') \geq k$. Since $bb_m$ is monotonic, we would have $bb_m(n) \geq k$. So $k$ would not satisfy $bb_m(n) < k < bb_m(n+1)$.

 

[SSequence]

...
A potential problem that "might" exist here is to guarantee that none of the points from bb(0) to bb(n-1) will occur in this enumeration (while "sweeping" through between rows n and n+1). I am not quite confident about this either way, so I can't really say.
...

Upon a second thought, that might not be a problem. Denote the n-th row by R_n and (n+1)-th row by R_n+1.

As an example, consider bb(3). For it to be included, at some point n-th row must have value less than bb(3) and (n+1)-th row must have value greater than bb(3) (at the same point). That is more precisely there must be some value a so that:
R_n( a ) < bb(3)
R_n+1( a ) > bb(3)
However, the first time (n+1)-th row equals bb(3) is the same time at which the n-th row equals bb(3). That is:
R_n( bb(3) ) = bb(3)
R_n+1( bb(3) ) = bb(3)
Before this point both rows were less than this value. And if after that point (n+1)-th row has higher value than bb(3) while the n-th row stays at bb(3), that's not a problem because bb(3) will not be enumerated with this.

edit:
I don't quite get the necessity of setting the two argument function (in post#11) to 0. But anyway, the construction itself (or the basic idea of construction) seems convincing enough.

 

[SSequence]

I was thinking about an extension question with regards to OP. I haven't thought about the answer much till now so I can't say whether its difficulty is easy/normal/hard. So here is the problem statement that I came up with.

Describe a function bbb:N→N and denote its range as BBB (similar to before). It must have the following properties:
(1) The function bbb has basic properties of the function bb. That is:
(a) Is strictly increasing.
(b) Eventually grows strictly faster than any given recursive function (similar to bb).
(c) The set BBB and Halt are both equivalent to each other (in the sense that both are reducible to each other, similar to described in OP and later in thread).

(2) The set BBB is not co-r.e.

=====

If such a function bbb:N→N exists give its description and if it doesn't, show that it can't exist.

 

[SSequence]

Just to emphasize the motivation behind the question such as one in my previous post. Let K denote the diagonal set (we could use the Halt set in its place essentially). Consider a set A with the following description:

if x∉BB then x∉A

if x∈BB
then {
if x∈bb(a) for some a∈K
then x∈A
if x∈bb(a) for some a∈K' (complement of K)
then x∉A
}

=====

It would seem that this set A (along with associated function) has all the properties that I mentioned in point(1) in previous post. Then the same question could be asked for it that was asked in OP for the set BB.