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
    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?2012-08-05
  • 0
    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).2012-08-05
  • 0
    Even though that on the way for deciding it hiding not $R$ process?2012-08-05
  • 0
    not R proccess? do you mean enumerating $ M_i $? you are not enumerating all $ M_i $ just a finite subset of it.2012-08-05
  • 0
    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.2012-08-05
  • 0
    you are not cheking it. the hardest thing you are checking in the algorithm is if $ x = $ which is just a comparison of finite strings (since the encoding of $ $ is a string and so does $x$ since it is an input of the algorithm ). and as i said before the value $ k $ is known to be exist and that all you should care about.2012-08-05
  • 0
    I'm sorry, I didn't understand why does it have to exsit. I mean I can get $$ so I need to check $M_1,M_2,M_3,M_4>$ and to verify each one if it's language is all $\sum^*$, each checking is not decidable, why one of them must have as its language $\sum^*$? maybe the numbering is such that $M_1={1}, M_2={0},M_3={0000,0}, M_4={11,11}$?2012-08-05
  • 0
    no you just need to check wether 5 < k or not. if 5 < k then by the definition of k $ M_5 $ cant possibly have $j$ such that $ j < 5 $ and $ L(M_j) = \Sigma^* $ since then you would have a contradiction with the definition of k.2012-08-05
  • 0
    notice that "finding k" is not part of the algorithm2012-08-05