Awesome q2a theme
0 votes

Which of the following properties of recursive enumerable set is/are recursive enumerable

  1. L = Φ
  2. L contains at least 5 members
  3. L has exactly one member

Please explain

in Theory of Computation by (14 points) | 16 views

1 Answer

0 votes
A simple way to answer such questions is to remember couple of points:

1. If a language is RE : There should be a TM that can return "YES" every time the answer is YES.

2. If a language is REC: There should be a TM that halts. i.e. it should be able to return YES for all YES, and NO for all NO.

With this, try to answer the given question:

A. Not RE (and obviously not REC). Assume you have a TM. It should stop and say YES only if L indeed contains only $ \phi$ (i.e absolutely no strings should be accepted). Now, L might contain a string that the TM accepts after an infinite amount of time. In which case, the answer is not YES. And you have to wait an infinite amount of time to discover that (since you have to test an infinite number of strings, each of which may run for an infinite time). In other words, there is no way for you to say "YES, this language is empty and no string will be accepted".

B. RE (but not REC).  Generate all strings of L and feed them to a TM in order of length. Use dovetailing to reduce the time spent waiting. Once 5 strings are accepted by the TM, return YES. Hence RE (we are capable of returning YES once 5 strings are accepted).

C. Not RE (and obviously not REC). Say you have a TM. After feeding to it each string of the language, one string got accepted. Now can you answer YES? No, you cannot. Because there might be one more string somewhere down the line that will be accepted after some infinite duration. Hence not RE, since you cannot confidently answer YES for all YES scenarios. i.e you cannot confidently say the TM accepts only that one string and nothing else.


This is the intuitive way of answering such questions. For a formal method, you can answer such questions by a direct application of Rice's 2nd Theorem and the monotonicity property. You have to read up on it (there are good articles about this on GO).
by (1.9k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jun 2020
  1. vps123

    4 Points

  2. ummokkate

    1 Points

  3. Kushagra गुप्ता

    1 Points

  4. faseela45

    1 Points

  5. srestha

    1 Points

7,385 questions
1,744 answers
90,357 users