2
$\begingroup$

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.

  • 0
    see also http://cs.stackexchange.com/questions/367/how-can-it-be-decidable-whether-pi-has-some-sequence-of-digits2012-08-05

1 Answers 1

3

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 = $.
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

  • 0
    notice that "finding k" is not part of the algorithm2012-08-05