Decidable and Undecidable problems - Recursive and Recursively Enumerable Language

 

🧠  Decidable and Undecidable Problems?

In the context of Turing machines, every decision problem can be viewed as a language recognition problem.

A decision problem is any question that has a yes/no (true/false) answer —
for example:

“Does this Turing machine accept the string ‘101’?”

---

⚙️ 1. Decidable Problems (Recursive Languages)

A decidable problem is one for which there exists a Turing machine that:

• Always halts on every input, and

• Answers correctly whether the input belongs to the language or not.

In other words:

A language L is decidable (or recursive) if there exists a Turing machine M such that:

• For every string w in Σ*:

  • If w ∈ L, M accepts w.

  • If w ∉ L, M rejects w.

  • M halts in both cases.

🧩 Key property:
The machine never loops forever — it always halts with a yes/no answer.

---

✅ Examples of Decidable Problems

1. Membership problem for finite automata

   • Given a DFA D and a string w, does D accept w?
     ✅ Decidable — we can simply simulate D on w and check.

2. Emptiness problem for DFA

   • Does DFA D accept any string at all?
     ✅ Decidable — check if there’s a path from the start state to a final state.

3. Equivalence of two regular expressions or DFAs
   ✅ Decidable — by minimizing both automata and comparing them.

4. Halting on short input

   • “Does this Turing machine halt on input ‘ε’ (empty string) within 100 steps?”
     ✅ Decidable — we can simulate it for 100 steps and check.

---

🚫 2. Undecidable Problems (Non-Recursive Languages)

A problem is undecidable if no Turing machine can solve it for all possible inputs —

that is, no algorithm can always give a correct yes/no answer and halt for every case.

Formally:

A language L is undecidable if there is no Turing machine that halts on all inputs and decides whether w ∈ L.

---

❌ Examples of Undecidable Problems

1. The Halting Problem

   Given a Turing machine M and an input w, does M halt on w?

   🧩 This is undecidable — proved by Alan Turing using a diagonalization argument.
   There is no general algorithm that can determine for all (M, w) pairs whether M halts.

2. The Acceptance Problem

   Given a Turing machine M and a string w, does M accept w?

   This problem, often denoted $A_{TM} = \{ \langle M, w \rangle \mid M \text{ accepts } w \}$,
   is Turing-recognizable but undecidable.

3. The Emptiness Problem for Turing Machines

   Does a Turing machine M accept any string at all?
   ❌ Undecidable — no algorithm can determine this in general.

4. The Equivalence Problem for Turing Machines

   Given Turing machines M₁ and M₂, do they accept the same language?
   ❌ Undecidable — there is no general test for this.

---

🧩 Difference Between Decidable and Undecidable Problems

Feature	Decidable Problem	Undecidable Problem
Definition	Can be solved by a Turing machine that halts on every input	No Turing machine can solve it for all inputs
Language Type	Recursive (decidable) language	Non-recursive (undecidable) language
Halting Behavior	Always halts	May not halt or no TM exists
Example	DFA emptiness, string acceptance by DFA	Halting problem, TM equivalence
Output Guarantee	Always gives yes/no answer	May loop forever or never give an answer

---

🔁 Relation to Recognizable Languages

• Every decidable language is also Turing recognizable.
  (If a machine always halts, it can certainly recognize the language.)

• But not every recognizable language is decidable.
  (Some TMs recognize but may loop forever on inputs not in the language.)

---

💡 Intuitive Analogy

Concept	Analogy
Decidable	A well-defined question you can always answer by following a recipe — e.g., checking if a number is even.
Undecidable	A question for which no recipe can always give you an answer — e.g., predicting  whether an arbitrary computer program will stop running or loop forever.

---

🧾 Summary

Term	Meaning	Example
Decidable Problem	There exists a Turing machine that halts with yes/no answer for all inputs	DFA acceptance, regular expression equivalence
Undecidable Problem	No Turing machine can always decide the answer for all inputs	Halting problem, TM equivalence, emptiness of TM

🧠 1. Recursive (Decidable) Languages

Definition:

A language $L$ is recursive (also called decidable) if there exists a Turing Machine (TM) that:

• Always halts for every input string, and

• Accepts if the string is in $L$,

• Rejects if the string is not in $L$.

👉 In other words,
A recursive language corresponds to a decidable problem — we can always determine membership in finite time.

---

Example:

Let

$$L=\{w\mid w\text{ contains an equal number of 0s and 1s}\}$$

We can design a Turing Machine that:

• Scans the tape to find and cross out a 0 and a 1 each time,

• Repeats until all symbols are crossed out,

• Halts and accepts if the tape becomes empty, otherwise rejects.

✅ The TM always halts, so $L$ is recursive.

---

⚙️ 2. Recursively Enumerable (RE) Languages

Definition:

A language $L$ is recursively enumerable (RE) if there exists a Turing Machine that:

• Accepts every string $w\in L$

• May not halt if $w\mathrm{\notin }L$.

👉 In simple words:

• The machine can enumerate all the strings in the language.

• But if the string does not belong to the language, the TM may loop forever.

Hence, these languages correspond to semi-decidable problems — we can verify yes instances, but not necessarily no ones.

---

Example:

Let

$$L=\{⟨M,w⟩\mid M\text{ halts on input }w\}$$

This is the Halting Problem language.

• If the given TM $M$ halts on $w$, our simulator halts and accepts.

• If $M$ doesn’t halt, our simulator runs forever.

So $L$ is recursively enumerable (RE), but not recursive (because the halting problem is undecidable).

---

🔁 3. Co-Recursively Enumerable (Co-RE) Languages

Definition:

A language $L$ is co-recursively enumerable (co-RE) if its complement $\overline{L}$ is recursively enumerable.

That means:

• There exists a TM that halts and accepts when $w\mathrm{\notin }L$,

• But may run forever when $w\in L$.

---

Example:

Let $L = \{ \langle M, w \rangle \mid M \text{ does not halt on input } w \}$

This is the complement of the Halting Problem.
So:

• $\mathrm{L }$is co-RE,

• but not RE itself.

---

🧩 Relationship between Recursive, RE, and Co-RE Languages

Type	Halts on all inputs?	Accepts?	Rejects?	Example
Recursive	✅ Always	Halts and Accepts if in L	Halts and Rejects if not in L	DFA membership
Recursively Enumerable (RE)	❌ May loop	Halts and Accepts if in L	May loop forever if not in L	Halting Problem
Co-RE	❌ May loop	Halts and Accepts if not in L	May loop forever if in L	Complement of Halting Problem

---

📘 Summary 

• Recursive (Decidable): TM halts on all inputs → problem solvable by algorithm.

• Recursively Enumerable (Semi-decidable): TM halts on yes inputs but may loop on no.

• Co-Recursively Enumerable: TM halts on no inputs but may loop on yes.

• Undecidable problems: belong to RE or co-RE but not recursive.

• Some problems are not even RE — no TM can recognize them.

Turing Decidable Problems Examples

(a) has at least 481 states?
(b) takes more than 481 steps on input epsilon?
(c) takes more than 481 steps on some input?
(d) takes more than 481 steps on all inputs?
(e) ever moves its head more than 481 tape cells away from the left endmarker on input epsilon?

Turing Undecidable Problems Examples

(f) accepts the null string e?

(g) accepts any string at all?

(h) accepts every string?

(i) accepts a finite set?

(j) accepts a regular set?

(k) accepts a CFL?

(1) accepts a recursive set?

(m) is equivalent  to a Turing machine with a shorter description.