# Recursively Enumerable Sets & Turing Machine

**TURING MACHINE**

**Configuration of TM**

R/W head can move in any direction but it moves at a time one cell, this capability is called "turn around capability".

**Specification**

The turing machine can be represented as a 7 tuple as follows:

M=( Q , ∑ , Ꚍ , Ᵹ , q

_{0 ,}B , F)

Where ,

Q = set of states.

∑ = input alphabet.

Ꚍ = tape alphabet

Ᵹ = transition function ; for DTM Ᵹ : Q x Ꚍ ---> Q x Ꚍ x { L , R}

B = blank symbol

F = final states F is subset of Q

Closure properties of Recursive Language

**Recursive language are closed under the following properties:**

(a) Union operation

(b) Intersection operation

(c) Complement

(d) Concatenation operation

(e) Kleene closure

(f) Positive closure

(g) Difference , symmetric difference , XOR , NAND , NOR and any other operation which can be reduced to intersection and complement.

(h) Reversal (transpose) operation

**Recursive language are not closed under following properties:**

(a) Homomorphism of a recursive language.

(b) Substitution of a recursive language.

**Closure Properties of Recursive Enumerable Language**

Recursive Enumerable language are closed under the following properties:

(a) Union operation

(b) Intersection operation

(c) Concatenation operation

(d) Kleene closure

(e) Reversal operation

(f) Positive closure

**Recursive enumerable language are not closed under following properties:**

(a) Complement

(b) Difference , symmetric difference , XOR , NAND , NOR and any other operation which can be reduced to intersection and complement

**Decidability Problems for Recursive Language**

1. Membership problem : Decidable

2. Emptiness problem: Undecidable.

3. Finiteness problem: Undecidable.

4. Equivalence problem: Undecidable.

5. Subset Problem: Undecidable.

6. Ambiguity problem: Undecidable.

7. Regularity problem: Undecidable.

8. Universality problem L = ∑*? : Undecidable.

9. Disjointedness problem: Undecidable.

**Some decidability problems related to halting turing machines ( REC language)**

1. Halting problem of a (halting) turing machine : Decidable.

2. Empty word halting problem for halting turing machine: Decidable

3. State entry problem for halting turing machine: Decidable.

**Decidability Problems for Recursively Enumerable Languages**

1. RE membership problem: Undecidable

2. Emptiness problem: Undecidable.

3. Finiteness problem: Undecidable.

4. Equivalence problem: Undecidable.

5. Subset problem: Undecidable.Undecidable. Undecidable.

6. Universality problem: Undecidable.

7. Ambiguity problem: Undecidable.

8. Regularity problem: Undecidable.

9. Disjointedness problem: Undecidable. Undecidable.

**Some decidability problems related to turing machines (RE languages)**

1. Halting problem of a turing machine : Undecidable.

2. Empty- word halting problem: Undecidable.Undecidable. Undecidable.

3. State entry problem: Undecidable.

4. Post correspondence problem: Undecidable.

5. Modified post correspondence problem (MPCP): Undecidable.

**Post correspondence problem :**An instance of PCP consist of 2 lists, A = W

_{1………………..Wn}

_{and B = X1 ...............X2 of strings over some alphabet }

_{∑ . This instance of PCP has a solution if there is any sequence of integers }I

_{1 .}

_{}

_{}

## No comments