$n$-r.e. plus left-r.e.

Definitions

Let $A\subset\omega$. $A$ is $n$-r.e. if there is a computable function $f(a,s)$ such that for all $a\in\omega$,

• $f(a,0)=0$,
• $|\{s:f(a,s)\neq f(a,s+1)\}|\leq n$,
• $\lim_{s\to\infty}f(a,s)=\chi_A(a)$.

Note that $1$-r.e. sets are just r.e. sets; $2$-r.e. sets are also called d.r.e. sets, which are the differences of two r.e. sets.

$A$ is left-r.e. if the corresponding real $\alpha=\sum_{a\in A}2^{-a}$ is a left-r.e. real. That is, $\{q\in\mathbb{Q}:q<\alpha\}$ is an r.e. set.

The first $n$ bits of $A$, denoted by $A\upharpoonright_n$, is the $n$-bit binary string $\chi_A(0)\chi_A(1)\cdots\chi_A(n-1)$.

Let $A,B\subset\omega$. $A$ is ibT-reducible to $B$, written $A\leq_{ibT}B$, if there is a partial computable function $f$ that maps $B\upharpoonright_n$ to $A\upharpoonright_n$ for each $n$.

$A$ is rK-reducible to $B$, written $A\leq_{rK}B$, if there is a constant $k$ and a partial computable function $f$ that maps $B\upharpoonright_n$ to an index $e$, such that $|W_e|\leq k$ and $A\upharpoonright_n\in W_e$, where $W_e$ is the $e^\text{th}$ r.e. set.

$A$ is ibT-equivalent to $B$, written $A\equiv_{ibT}B$, if $A\leq_{ibT}B$ and $B\leq_{ibT}A$. Same for $\equiv_{rk}$.

Known facts

Fact. Every $2$-r.e. and left-r.e. set is ibT-equivalent (and thus rK-equivalent) to an r.e. set.

Fact. There is a $3$-r.e. and left-r.e. set, which is not ibT-equivalent to any r.e. set.

The problem

Question. Is every $3$-r.e. and left-r.e. set rK-equivalent to an r.e. set? Or, is there a $3$-r.e. and left-r.e. set that is not rK-equivalent to any r.e. set?

Any answer changing the $3$-r.e. assumption to $4$-r.e., or $n$-r.e. for even larger $n$, may also be useful.

Relevant contents

• open problem - Even Number Game