Recursively Enumeration and Recursive Language

Language accepted by TM are called as Recursively enumerable language.The context free langauage are subset of recursively enumeration language,Just keep in mind that we are not considering the language having epsilon.




Theorem1: A Langauge is recursive if and only if it can be effectively enumerated in lexicographic order(i.e alphabet order). The String of a language L can be effectively enumerated mean,a turing machine exist for a language L which will enumarate all valid string of the language. Theorem2: If a language L and its complement L' are both recursively enumerable then both language are recursive .If L is recursive then L' is also recursive and consequently both are recursively enumerable.


Recursively Enumerable (RE)language are closed under following operation:


Suppose L and P are two RE language then these are recursively enumerable :

1) L of L

2) Concatenation L.P

3)Union L∪P

4) Intersection L∩P



      Recursively enum language are not closed under

1) Set difference

2) Complementation


Modification to standard TM

By doing some modification to the standard tuning machine we are not able to accept any new langauge which are not accepted previously by the standard TM. Whatever the accepted by TM are now accepted by the new modification,Infact some of modification are actually reducing the power. Some of the modification to standard TM after which the power remain same.




Definition of Tuning Machine
  1. A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected. A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −
    Q is a finite set of states
    X is the tape alphabet
    ∑ is the input alphabet
    δ is a transition function
    δ : Q × X → Q × X × {Left_shift, Right_shift}.
    q0 is the initial state
    B is the blank symbol
    F is the set of final states
  2. For Example tuning machine for anbn:
  3. NOTE1: 1)if a string is not in the langauge then you are going to hit dead configuration (configuration not defined for that input value) therefore turing machine will halt in non final state.So string wiil not be accepted. 2)we need not define every configuration like in DFA. 3)TM can be used as transduser of 1's complement, transduser of 2's complement,adder,comparator.
  4. NOTE2: writing complex TM by using these bsic TM which can do addition and comparison we can implement any mathematical function.TM is mathematical complete.
  5. Non Halting turing machine: