Is every recursively enumerable set many-one reducible to $L_\text{b}$? A URM $M$ b-accepts an input $x$ if in the overall course of its computation on $x$, the register $R_1$ contains only finitely many different values (thus, if $M$ halts on $x$, it always b-accepts, but the converse is not necessarily true). Let$$L_\text{b} := \{(x, y) : M_x \text{ b-accepts }y\}$$($M_x$ is the URM with code $x$).
Is every recursively enumerable set many-one reducible to $L_\text{b}$?
 A: Yes, every recursively enumerable set is many-one reducible to $L_\text{b}.$
If $A$ is a recursively enumerable set, then $A$ is the domain of some partial recursive function. Since URMs are Turing complete, there is some URM $M$ which halts on an input $n$ iff $n\in A$ (input $n$ means that we start $M$ with $R_1$ equal to $n$ and all the other registers equal to $0).$
To show that $A$ is many-one reducible to $L_\text{b},$ we exhibit a recursive function $f$ such that $n\in A$ iff $f(n)\in L_\text{b}.$ Here's how to define such an $f\!:$
For any input $n,$ $f(n)$ will be a pair $\langle s,0\rangle,$ where $s$ is the code for the URM with the following program:


*

*First increment $R_2$ $n$ times. (This is $n$ separate instructions.)

*Then copy the instructions of the machine $M$ except:
(a) Replace every reference to a register $R_m$ with a reference to $R_{m+1}.$
(b) Change any jump to statement #$s$ with a jump to statement #$(2s+n).$ (This adjustment is necessary because of the extra statements introduced.)
(c) Immediately before each (modified) instruction of $M,$ insert an instruction "Increment $R_1\!$".
You can check that $f$ has the required property. In fact, the function $f$ is 1-1, so this actually demonstrates one-one reducibility (which is stronger than many-one reducibility).

Here's how the URM coded by $s$ works, assuming all registers are initialized to $0\!:$
$\bullet\;$ It first puts the number $n$ into $R_2$ $(R_2$ starts at $0$ and is incremented $n$ times).
$\bullet\;$ At this point, ignoring for now the effect of the extra "increment-$R_1\!"$ instructions, the machine follows the exact same computation as $M$ would do, except that it uses registers $R_2, R_3, R_4, \dots$ instead of $R_1, R_2, R_3, \dots$ (leaving $R_1$ free for another purpose). Since, immediately before this emulation of $M$ starts, $R_2$ is set to $n$ and the later $R_k\text{'s}$ are all $0,$ this is the computation that $M$ would make on input $n.$ Note that this computation halts iff $n\in A.$
$\bullet\;$ The interspersed instructions that increment $R_1$ do not affect the emulation of $M$ at all, since the emulation of $M$ only uses registers $R_k$ for $k \ge 2.$ So, first of all, the overall computation (including the extra increment instructions) really does halt iff $n\in A.$ The effect of the extra increment instructions is merely to keep a count in $R_1,$ adding $1$ to it for each step of the $M$-simulation.
We can conclude that the following are equivalent:
(i) $R_1$ takes only finitely many values in the course of the computation.
(ii) The URM executes only finitely many steps; that is, the URM halts. (The input given to the URM is irrelevant here; since the input is given in $R_1,$ the only effect of the input is where the instruction count in $R_1$ starts.)
(iii) $n\in A.$
Finally, for any $n,$ $f(n)$ is the ordered pair $\langle s,0\rangle,$ where $s$ is as above. So $f(n)\in L_\text{b}$ iff $R_1$ gets only finitely many values in the course of  the computation of the URM coded by $s$ when given input $0,$ which we know is true iff $n\in A,$ as desired.

It's probably worth pointing out that $b$-acceptance is very different from the standard notion of acceptance. The set $L_\text{b}$ isn't even recursively enumerable. (Its complement isn't recursively enumerable either.) I haven't thought through the details, but I believe that $L_\text{b}$ is a complete $\Sigma^0_2$ set and so has Turing degree $0''.$ (I think it's Turing equivalent, and probably recursively equivalent, to $\{ x \mid W_x \text{ is finite}\},$ where $W_x$ is the r.e. set coded by $x.)$
