---
title: "Recursive and recursively enumerable languages"
subject: "Theory of Computation"
chapter: 4
key: "semester_3/theory_of_computation:recursive-vs-re-examples"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/recursive-vs-re-examples
site: BCT Engineering
---

# Recursive and recursively enumerable languages

Theory of Computation · Chapter 4: Turing Machine

- Asked in: 2074 Asoj
- Video: [Recursive & Recursively Enumerable Sets](https://www.youtube.com/watch?v=t1lTeKR4ESk) — TutorialsPoint
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/recursive-vs-re-examples
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-4

## Question

Explain recursive and recursively enumerable languages with suitable examples of each language.

## Short answer

Recursively enumerable languages are accepted by a Turing machine that may loop on non-members. Example: the halting language {⟨M,w⟩ | M halts on w}. Recursive languages are decided by a TM that always halts; examples include {aⁿbⁿcⁿ} and the primes. Every recursive language is RE, but not every RE language is recursive.

## Answer

#### Recursively enumerable (RE) languages
A language L is **recursively enumerable** (Turing-recognisable) if some Turing machine M accepts it: for w ∈ L, M halts in an accepting state; for w ∉ L, M either halts in a non-accepting state or **runs forever**. M recognises L but need not decide it.

**Example:** the halting language H = { ⟨M, w⟩ : M halts on input w }. Simulate M on w; if the simulation halts, accept. If M loops, the simulator loops. So H is RE but not recursive.

#### Recursive languages
A language L is **recursive** (decidable) if some TM M **halts on every input**, accepting w ∈ L and rejecting w ∉ L. Such a machine is an algorithm.

**Examples:**
- { aⁿbⁿcⁿ : n ≥ 1 }: mark one a, one b, one c repeatedly and check nothing remains. It always halts.
- The set of prime numbers (in binary or unary): try all possible divisors; this halts.
- Every regular language and every context free language is recursive.

#### Relationship
```text
 all languages
 ┌──────────────────────────────┐
 │  RE languages                │
 │  ┌────────────────────────┐  │
 │  │ recursive languages    │  │
 │  │  ┌──────────────────┐  │  │
 │  │  │ CFL ⊃ regular    │  │  │
 │  │  └──────────────────┘  │  │
 │  └────────────────────────┘  │
 │   (H lies here: RE, not rec.)│
 └──────────────────────────────┘
```
- Every recursive language is RE, but not every RE language is recursive.
- L is recursive if and only if both L and its complement are RE.
- The complement of H is not RE, so it lies outside RE.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is the behaviour of a TM for an RE language on w not in L?
   A. It always rejects
   B. It may halt and reject or run forever
   C. It always accepts
   D. It always loops
   Answer: B. RE only requires halting and accepting on members; on non-members the machine may loop. (Key point: RE definition)

2. Why is the halting language H = {<M,w>} RE but not recursive?
   A. Simulating M on w halts exactly when M halts, but if M loops the simulator loops too
   B. It is finite
   C. It is regular
   D. Its complement is RE
   Answer: A. Simulation accepts members but cannot detect looping, so no decider exists. (Key point: Halting language)

3. Which is an example of a recursive language from the answer?
   A. The halting language
   B. Complement of the halting language
   C. The set of primes in binary
   D. The set of all TM descriptions that halt
   Answer: C. Primality is decided by trying all divisors, which always halts. (Key point: Recursive example)

4. What is true of the complement of H?
   A. It is recursive
   B. It is not RE
   C. It is regular
   D. It is context free
   Answer: B. If H is RE but not recursive, its complement cannot be RE. (Key point: Relationship)

## Related in Theory of Computation

- [Recursive iff language and complement are RE](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-iff-complement-re) — Theory of Computation, chapter 4, asked 2×
- [Recursive language and its properties](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Arecursive-language-properties) — Theory of Computation, chapter 4, asked 2×

## Related in other subjects

- [High level languages and natural language](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Ahll-similar-natural-language) — Computer Programming, chapter 1
- [High level languages; C versus FORTRAN](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Ahll-types-c-vs-fortran) — Computer Programming, chapter 1
- [Categories of programming languages](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Acategorise-languages) — Computer Programming, chapter 1