## Recent Post

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 , ∑ , Ꚍ , Ᵹ , q0 , 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 = W1………………..Wn
and B = X1 ...............X2 of strings over some alphabet ∑ . This instance of PCP has a solution if there is any sequence of integers I1 .