As an imprecise lower bound one can take the least $\Pi^1_0$-reflecting ordinal mentioned above. (If $\gamma$ is this ordinal, and so we have $L_\gamma \prec_{\Sigma_1}L_{\gamma +1}$, it is easy to see all ordinals $\tau < \gamma$ are p.r. recog. as for any such $\tau$ there is some sentence $B$ so that $L_\tau$ is the least level of the $L$-hierarchy where $B$ is true. But $\gamma+1$ is itself p.r. recog. as the first $\tau$ where $L_\tau$ has a proper $\Sigma_1$-substructure, etc., etc. (This answers the second part of the original Question) Similar statements hold for larger stretches of the ordinals $[0,\gamma']$ for $\gamma + 1 < \gamma'$.)

[1] R.B. Jensen and C. Karp Primitive Recursive set functions, in Proceedings of Symposia in Pure Mathematics,vol.13 Part 1, "Axiomatic Set Theory", Ed. D. Scott, AMS, 1971, pp 143-167.

As an imprecise lower bound one can take the least $\Pi^1_0$-reflecting ordinal mentioned above. [Edit: This is fully answered below at (C).] (If $\gamma$ is this ordinal, and so we have $L_\gamma \prec_{\Sigma_1}L_{\gamma +1}$, it is easy to see all ordinals $\tau < \gamma$ are p.r. recog. as for any such $\tau$ there is some sentence $B$ so that $L_\tau$ is the least level of the $L$-hierarchy where $B$ is true. But $\gamma+1$ is itself p.r. recog. as the first $\tau$ where $L_\tau$ has a proper $\Sigma_1$-substructure, etc., etc. (This answers the second part of the original Question) Similar statements hold for larger stretches of the ordinals $[0,\gamma']$ for $\gamma + 1 < \gamma'$.)

[1] R.B. Jensen and C. Karp Primitive Recursive set functions, in Proceedings of Symposia in Pure Mathematics,vol.13 Part 1, "Axiomatic Set Theory", Ed. D. Scott, AMS, 1971, pp 143-167.

Edit added to address Gro-Tsen's queries (see comment below) and intended to complete both the original Question and its second reformulation:

(A) The function $F(\delta)=L_\delta$ is p.r. (See Devlin, "Constructibility" but I think it is in [1] anyway.) Satisfaction is likewise p.r., hence the function:

$G(\delta)=1$ if $L_\delta \vDash $ '' $A\wedge \forall\delta' L_{\delta'} \vDash \neg A$'';

$G(\delta)=0$ otherwise

is p.r. and gives that the least $\delta$ with $L_\delta\vDash A$ is p.r. recognizable.

(B) Let $\beta<\sigma_1$ . We want that $\beta$ is p.r. recognizable*. Let $A$ be a $\Sigma_1$ sentence that is first true at some $\gamma \in (\beta, \sigma_1)$. By standard arguments the $<_L$-least bijection $f_\gamma:\omega\leftrightarrow \gamma$ is definable over $L_\gamma$. Suppose $f_\gamma(n)=\beta$. By the kind of argument in (A) we see that $ \gamma$ is p.r. recog*. But then so is $L_{\gamma+1}$ and $f_\gamma$. Put these facts together to build a p.r. function $G$ whose only non-zero value is $G(\gamma)=\beta$.

(C) We answer this (and, using the first Lemma above, finish the original Question) by:

Lemma Let $\alpha < \beta_0$. Then $\alpha$ is p.r. recog. Hence the least p.r. reflecting ordinal is $\beta_0$ which in turn is the least non-p.r. recog. ordinal.

Proof: Say that $\alpha$ begins a gap if $\exists \delta ( L_\alpha \prec_{\Sigma_1} L_\delta)$. We say that $[\alpha,\delta]$ is a gap, if $\alpha$ begins a gap, and $\delta$ is maximal with $L_\alpha \prec_{\Sigma_1} L_\delta$.

$\bullet$ If $\omega < \delta < \beta_0$ is not in any gap, then we are sufficiently low down in the $L$-hierarchy where there is a $\Sigma_1$ sentence $A=A(\delta)$ so that

$L_{\delta+1}\vDash $ ``$A\wedge\forall \delta’<\delta L_{\delta’ + 1}\vDash \neg A$ ‘’. As argued above at (A), this makes $\delta+1$ and so $\delta$ p.r. recog.

We just need the ordinals of gaps $[\alpha,\delta]$ with $\alpha <\beta_0$ to be p.r. recognizable.

So let $[\alpha,\delta]$ be such a gap. We show that $\alpha$ is p.r. recog. and variants of the argument suffice for the other ordinals in the gap. Then $\alpha < \delta < \alpha^* <\beta_0$. Using (un)/pairing functions (which are p.r.) etc. one has that the closure of $\{\alpha\}$ under p.r. functions includes all ordinals up to $\alpha^*$. So let $F$ be a p.r. function, with $F(\alpha)=\delta’$ for some $\delta’\in (\delta,\alpha^*)$. Let $A=A(\delta’)$. Let:

$G(\xi) = 1$ if $L_{F(\xi)+1}\vDash A$;

$G(\xi) = 0$ otherwise.

Then $G$ witnesses that $\alpha$ is p.r. recognizable, so we are done. Q.E.D.

(The definition of $\beta_0$ and $\beta$ is that given in Gro-Tsen's second formulation of question, in terms of the Veblen function (if I understand the terms correctly).)

This gives an upper bound to the first p.r. reflecting, and so non-p.r. recognizable, ordinal, and answers the first part of the Extra Quest. negatively.

As an imprecise lower bound one can take the least $\Pi^1_0$-reflecting ordinal mentioned above. (If $\gamma$ is this ordinal, and so we have $L_\gamma \prec_{\Sigma_1}L_{\gamma +1}$, it is easy to see all ordinals $\tau < \gamma$ are p.r. recog. as for any such $\tau$ there is some sentence $B$ so that $L_\tau$ is the least level of the $L$-hierarchy where $B$ is true. But $\gamma+1$ is itself p.r. recog. as the first $\tau$ where $L_\tau$ has a proper $\Sigma_1$-substructure, etc., etc. (This answers part of the original Question) Similar statements hold for larger stretches of the ordinals $[0,\gamma']$ for $\gamma + 1 < \gamma'$.)

To find the least upper bound of the p.r. unrecog. ordinals, one can reason as follows:

This gives an upper bound to the first p.r. reflecting, and so non-p.r. recognizable, ordinal, and will answer the first part of the Extra Quest. negatively, as we shall see below there are p.r. recognisable ordinals $>\beta$.

As an imprecise lower bound one can take the least $\Pi^1_0$-reflecting ordinal mentioned above. (If $\gamma$ is this ordinal, and so we have $L_\gamma \prec_{\Sigma_1}L_{\gamma +1}$, it is easy to see all ordinals $\tau < \gamma$ are p.r. recog. as for any such $\tau$ there is some sentence $B$ so that $L_\tau$ is the least level of the $L$-hierarchy where $B$ is true. But $\gamma+1$ is itself p.r. recog. as the first $\tau$ where $L_\tau$ has a proper $\Sigma_1$-substructure, etc., etc. (This answers the second part of the original Question) Similar statements hold for larger stretches of the ordinals $[0,\gamma']$ for $\gamma + 1 < \gamma'$.)

To find the least upper bound of the p.r. recog. ordinals, one can reason as follows: