Recursive and Recursively Enumerable Languages | पुनरावर्ती और पुनरावर्ती रूप से गणनीय भाषाएँ

Recursive और Recursively Enumerable (RE) भाषाएँ Turing Machine की computational क्षमता को दर्शाती हैं। ये दोनों भाषाएँ यह निर्धारित करती हैं कि कौन सी समस्याएँ algorithmically हल की जा सकती हैं और कौन सी नहीं। इस अवधारणा के माध्यम से हम Computability और Decidability के बीच का अंतर समझते हैं।

1️⃣ परिचय / Introduction

Computation theory में, हर भाषा किसी न किसी प्रकार की Turing Machine द्वारा पहचानी जाती है। यदि कोई Turing Machine किसी string के लिए हमेशा निर्णय (accept/reject) लेकर halt करती है, तो वह भाषा Recursive Language कहलाती है। लेकिन यदि Turing Machine केवल भाषा में आने वाली strings के लिए halt करती है और बाकी के लिए infinite loop में चली जाती है, तो वह भाषा Recursively Enumerable Language कहलाती है।

2️⃣ परिभाषा / Definitions

(A) Recursive Language (Decidable Language):

ऐसी भाषा जिसके लिए कोई Turing Machine मौजूद है जो हर input पर halt करती है और निर्णय (accept/reject) देती है। अर्थात, Machine कभी infinite loop में नहीं जाती।


L is Recursive ⇔ ∃ TM M such that:
∀ w ∈ Σ*, 
  M halts and 
  M accepts w if w ∈ L
  M rejects w if w ∉ L

(B) Recursively Enumerable Language (Semi-Decidable Language):

ऐसी भाषा जिसके लिए कोई Turing Machine मौजूद है जो केवल उन strings के लिए halt करती है जो भाषा में आती हैं। यदि input भाषा में नहीं है, तो Machine कभी halt नहीं करती।


L is RE ⇔ ∃ TM M such that:
∀ w ∈ Σ*,
  M halts and accepts w if w ∈ L
  M may loop forever if w ∉ L

3️⃣ उदाहरण / Example

Example 1:

Language L₁ = {aⁿbⁿ | n ≥ 1} यह Recursive है क्योंकि Turing Machine हर input पर accept या reject करके halt करती है।

Example 2:

Language L₂ = {⟨M, w⟩ | Turing Machine M accepts w} यह Recursively Enumerable है क्योंकि Machine केवल तब halt करती है जब M w को accept करता है, अन्यथा infinite loop में जाती है।

4️⃣ Recursive और RE में अंतर / Difference between Recursive and RE Languages

पहलू	Recursive Language	Recursively Enumerable Language
Definition	TM halts on every input	TM halts only for accepted inputs
Decidability	Decidable	Semi-decidable
Halting	Always halts	May not halt
Complement	Recursive	Not necessarily RE
Example	L = {aⁿbⁿ}	L = {⟨M, w⟩ \| M accepts w}

5️⃣ संबंध / Relationship between Recursive and RE

हर Recursive Language एक Recursively Enumerable Language होती है।
लेकिन हर RE Language जरूरी नहीं कि Recursive हो।

Mathematically:


Recursive ⊂ Recursively Enumerable

6️⃣ भाषा का पूरक / Complement of Language

यदि L Recursive है, तो उसका complement L' भी Recursive होगा।
लेकिन यदि L RE है, तो L' जरूरी नहीं कि RE हो।

Example:

Halting Problem की भाषा Lₕ RE है लेकिन उसका complement Lₕ' RE नहीं है।

7️⃣ Recursive और RE Languages की विशेषताएँ / Properties

Recursive Languages बंद होती हैं (closed) union, intersection, और complement पर।
RE Languages union और intersection पर बंद होती हैं, लेकिन complement पर नहीं।
Recursive Languages decidable problems को दर्शाती हैं।
RE Languages semi-decidable problems को दर्शाती हैं।

8️⃣ उदाहरण द्वारा व्याख्या / Example Explained

मान लें हमारे पास Turing Machine M है जो किसी भाषा L को accept करती है।

यदि M हर input के लिए halt करती है → L Recursive है।
यदि M केवल valid strings के लिए halt करती है → L Recursively Enumerable है।

9️⃣ उपयोग और महत्व / Applications and Importance

Algorithmic problem solving में सीमाएँ निर्धारित करना।
Halting Problem और Undecidability proofs में उपयोग।
Artificial Intelligence में decision boundaries की व्याख्या।
Compiler Theory और Formal Verification में उपयोग।

🔟 निष्कर्ष / Conclusion

Recursive और Recursively Enumerable भाषाएँ computation theory की मूलभूत अवधारणाएँ हैं। Recursive भाषाएँ पूरी तरह decidable होती हैं जबकि RE भाषाएँ केवल पहचान योग्य होती हैं। इन दोनों के अध्ययन से हमें यह समझ आता है कि कंप्यूटर किन समस्याओं को algorithmically हल कर सकता है और किन्हें नहीं।

Recursive and Recursively Enumerable Languages

In computation theory, Recursive and Recursively Enumerable (RE) languages define the boundary between what is algorithmically solvable and what is only recognizable.

1️⃣ Introduction

A language is called Recursive if there exists a Turing Machine that halts on every input and decides membership. A language is Recursively Enumerable if a Turing Machine halts only for strings in the language and may loop forever otherwise.

2️⃣ Formal Definitions

Recursive Language:


L is Recursive ⇔ ∃ TM M such that:
∀ w ∈ Σ*, M halts and accepts/rejects w

Recursively Enumerable Language:


L is RE ⇔ ∃ TM M such that:
∀ w ∈ Σ*, M halts if w ∈ L
M may loop if w ∉ L

3️⃣ Examples

L₁ = {aⁿbⁿ | n ≥ 1} → Recursive
L₂ = {⟨M, w⟩ | M accepts w} → Recursively Enumerable

4️⃣ Comparison Table

Feature	Recursive	Recursively Enumerable
Decision	Always halts	Halts only on valid input
Decidability	Decidable	Semi-decidable
Complement	Recursive	Not necessarily RE
Closure	Union, Intersection, Complement	Union, Intersection

5️⃣ Relationship


Recursive ⊂ Recursively Enumerable

6️⃣ Importance

Defines limits of algorithmic computation.
Basis for undecidability and halting problems.
Used in complexity classification.

7️⃣ Example Discussion

If a TM halts on every input → Recursive Language. If a TM halts only for accepted inputs → Recursively Enumerable Language.

8️⃣ Applications

Mathematical logic and computability proofs.
Design of decision algorithms.
Analysis of halting and undecidable problems.

🔟 Conclusion

Recursive and Recursively Enumerable languages distinguish between decidable and semi-decidable problems. They form the theoretical basis for understanding computation limits and the nature of algorithmic reasoning in computer science.