0

I have three related questions. The first two are extremely similar. The third one asks a question based on the first two. Let $K$ denote the diagonal halt set. Similarly let $bb:\mathbb{N} \rightarrow \mathbb{N}$ denote the busy beaver function and let $BB$ be the the set representing the image-set of the function $bb$.

(Q1) Define a set $A$ as follows:

if $x \notin BB$ then $x \notin A$

if $x \in BB$ then:

(a) if $x=bb(a)$ for some $a\in K$ then $x\in A$

(b) if $x=bb(a)$ for some $a\in K'$ then $x\notin A$

The question is simply whether $A$ is (i) co-r.e. OR (ii) neither r.e. nor co-r.e.?

(Q2) Define a set $B$ as follows:

if $x \notin BB$ then $x \notin B$

if $x \in BB$ then:

(a) if $x=bb(a)$ for some $a\in K$ then $x\notin B$

(b) if $x=bb(a)$ for some $a\in K'$ then $x\in B$

The question is simply whether $B$ is (i) co-r.e. OR (ii) neither r.e. nor co-r.e.?

(Q3) Does there exist a function $f:\mathbb{N} \rightarrow \mathbb{N}$ (denote the corresponding image-set as $F$) with the following properties: (i) $f$ is strictly increasing (ii) $f$ eventually grows faster any recursive function (iii) $F \equiv_T K$ (iv) $F$ is not co-r.e.

What I do know for sure is that if we replace $K$ with any recursive set the answer to both (Q1) and (Q2) is co-r.e. But because $K$ is not recursive, I do not know the answer. Though I guess(?) at least one of (Q1) and (Q2) has to be simpler than the other? (perhaps I should have given it more thought before posting the question)

SSequence
  • 1,022
  • The answer to Q2 may depend on the exact versions of $bb$ and $K$ you are using. Is $bb(n)$ approximately $f(n)=$least $s$ such that $K_s \cap [0,n] = K \cap [0,n]$? – realdonaldtrump Feb 22 '18 at 08:52
  • @realdonaldtrump You can replace $K$ by $H$ and $bb$, $BB$ by $bbb$, $BBB$ respectively in the original question. The condition for $H$ is $H \equiv_T K$. The condition for $bbb:\mathbb{N} \rightarrow \mathbb{N}$ is (i) it dominates every total recursive function (after finite number of initial values) (ii) It is strictly increasing (iii) $BBB \equiv_T K$. $BBB$ is the image-set of the function $bbb$. If the answer can be made ambiguous by the choice of $H$ or $bbb$ then one can given two specific examples and show how both answers are possible. – SSequence Feb 22 '18 at 13:23
  • Also $H$ should be a r.e. set. – SSequence Feb 22 '18 at 13:58
  • I posted this question on overflow: https://mathoverflow.net/questions/293752 – SSequence Feb 24 '18 at 20:20

0 Answers0