Language Accepted By Turing machine

 

🧠 What Does It Mean for a Turing Machine to Accept a Language?

A Turing Machine (TM) is like a computer that reads an input string (made up of symbols from an alphabet) and tries to decide whether that string belongs to a particular language.

---

🔹 Example Idea

Think of a language as a set of words — for example:

$$L = \{ a^n b^n \mid n \ge 1 \} = \{ ab, aabb, aaabbb, \ldots \}$$

A Turing machine $M$ is built in such a way that it can recognize the words in $L$.

---

⚙️ How the Turing Machine Works

1. The input string (like aabb) is written on the tape.

2. The machine starts in its start state.

3. It repeatedly follows the transition function δ, which tells it:

   • what to write on the tape,

   • whether to move left or right,

   • and which new state to go to next.

4. The machine continues until it reaches either:

   • the accepting state → ✅ (the string is accepted), or

   • the rejecting state → ❌ (the string is rejected).

If the machine never halts, it means it is still “thinking” forever.

---

📘 Definition (in Simple Words)

A string $w$ is accepted by a Turing Machine $M$ if,
starting with $w$ on the tape, $M$ eventually halts in its accepting state.

The set of all such strings is called the language accepted by $M$:

$$L(M) = \{ w \in \Sigma^* \mid M \text{ halts in the accepting state on } w \}$$

So —
👉 If $M$ halts and accepts $w$, then $w \in L(M)$.
👉 If $M$ halts and rejects $w$, or loops forever, then $w \notin L(M)$.

---

💬 Intuitive Meaning

The Turing Machine is like a checker:

• If the input fits the rule of the language, it accepts.

• If not, it rejects (or may never stop trying).

---

🔄 Recursively Enumerable (RE) Languages

A language is called recursively enumerable (or Turing-recognizable) if some Turing Machine accepts exactly that language.

That means:

• For every word in the language, the TM will halt and accept.

• For every word not in the language, the TM may either reject or loop forever.

Formally:

$$L \text{ is recursively enumerable } \iff \exists M \text{ such that } L = L(M)$$

---

🔹 Example

Let $L=\{a^n{b}^n\mid n\ge 1\}$

There exists a Turing machine that:

1. Checks each a is matched with one b.

2. If all match correctly, it halts in accept state.

3. Otherwise, it halts in reject state.

So, $L$ is recursively enumerable — because such a machine exists.

Recognizable vs. Decidable Languages

Kozen further distinguishes two classes:

1. Turing-Recognizable (Recursively Enumerable) Languages
   A language $L$ is Turing-recognizable if there exists a Turing Machine $M$ such that $L = L(M)$
   (The machine halts and accepts all strings in $L$, but may loop forever on others.)

2. Turing-Decidable (Recursive) Languages
   A language $L$ is Turing-decidable if there exists a Turing Machine $M$ that always halts and satisfies:

   • $M$ accepts all strings in $L$, and

   • $M$ rejects all strings not in $L$.

Thus:

$$\text{Decidable} \subsetneq \text{Recognizable}$$

---

✅ Decidable vs. Recursively Enumerable

Type of Language	What the TM Does
Decidable (Recursive)	Always halts — accepts or rejects every input.
Recursively Enumerable (RE)	Halts and accepts words in the language; may loop forever on others.

In short:
Every decidable language is recursively enumerable,
but not every recursively enumerable language is decidable.

---

🧩 Summary 

• A Turing Machine accepts a string if it halts in the accepting state.

• The set of all accepted strings forms the language accepted by the TM.

• A recursively enumerable language is one that can be recognized by some TM — meaning the machine halts for words in the language, but might loop forever otherwise.