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 .}