# why does $B=\{ \langle M_i: \exists j < i . L(M_j)=\sum^* \} \in R$?

I'd like your help with understanding how come the following language is decidable (in $R$).

Let $M_0,M_1,M_2,...$ numbering of all Turing machines over $\sum$, why does $B=\{ \langle M_i: \exists j < i . L(M_j)=\sum^* \} \in R$?

I understand that we have only have finite number of machines to go through for checking but the check itself for $L(M_j)=\sum^*$ is not decidable, and we might be stuck in infinite loop, so I thought that the language is in $co-RE \setminus R$, since we can check in parallel all the turing machines until $i$, and if $\exists j$ such that $L(M_j)\neq\sum^*$ stop and accept.

-
–  sdcvvc Aug 5 '12 at 11:12

Let $k = min \{ i : L(M_i) = \Sigma^* \}$ k exists since $M_i$ numbering starts the count from zero and the set is non empty, therefore we can construct the following algorithm:
Given input $x$ check if $x$ is a legal encoding of a turing machine and find $i$ (simply by searching in the numbering of the all turing machines since $x$ is legal encoding it should be in the numbering and the search should stop eventually) such that $x = <M_i>$.
then return False if $i \leq k$
or return True otherwise

therefore $B\in R$

we dont need to "know" k we only need to know he exists, and then hardcode its value into the algorithm, therefore we can construct such turing machine

-
Bar, thank you for the answer. I still don't understand how do you know if the turing machines that you chek on the way to i accepts all string in $\sum^*$, Don't you need to check it? –  Jozef Aug 5 '12 at 10:18
no you don't, you only need to prove existence of an "algorithm" which decides B. in other words proving the existence of k proves the existence of such algorithm (the definition of $R$ says it is all the languages such that there exists a turing machine which decides that language). you don't need to actually find k (compute it). –  bar Aug 5 '12 at 10:22
Even though that on the way for deciding it hiding not $R$ process? –  Jozef Aug 5 '12 at 10:33
not R proccess? do you mean enumerating $M_i$? you are not enumerating all $M_i$ just a finite subset of it. –  bar Aug 5 '12 at 10:50
I meant not a decidable process. even though though that I'm enumerating subset of it, enumerating even one for checking if it accepts all strings is not decidable. –  Jozef Aug 5 '12 at 11:21