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.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Range of Busy Beaver

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads - Range Busy Beaver | Date |
---|---|

A Estimation of Hurst Exponent Using Rescaled Range | May 4, 2017 |

Rescaled Range and "Persistence" | Jan 13, 2016 |

Range of one standard deviation from mean | Jun 14, 2014 |

Difference between codomain and range | Nov 9, 2012 |

Formulation of a score for how busy a person is | Aug 18, 2012 |

**Physics Forums - The Fusion of Science and Community**