REC and RE languages

Re: REC and RE languages

by Giorgio Satta -
Number of replies: 0

Here are the answers to the two questions.

  1. RE\REC is not empty. We will see some examples in chapter 9, that is, very soon. Let L be a language in RE\REC, and let M be a TM that recognises L. When we provide any string w as input to M, M will always halt and accept in case w is in L, and may not halt in case w is not in L.

  2. what do you mean when you say 'a string is computed'? Recall that you give a string w as input to a TM M, and M computes the answer, which is accept in case w is in L, and reject in case w is not in L. If the language recognised by M is in REC, the computation will always stop and you will always get an answer, which may be accept or reject. If the language recognised by M is in RE\REC, it might be the case that if w is not in L then M will never stop, so you do not get the reject answer.