REC and RE languages

REC and RE languages

by MANUEL LOVO -
Number of replies: 1

I don't understand a difference between REC and RE languages. 

1- Since the set of RE languages is larger than that of REC languages, i.e., REC is a subset of RE, what are the languages that differentiate these two? In RE\REC, there are languages that don't halt always. If this is correct, what can be an example of such a language? Are the strings in a language RE\REC only those for which computation may not end, or are there also strings for which computation ends?

2-If I understand correctly, a REC language halts all input strings, both in the language and not in the language. I'm not clear on an example of a string not in the language that is then computed and why, even if it's not in the language, it is computed.

In reply to MANUEL LOVO

Re: REC and RE languages

by Giorgio Satta -

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.