1.)A language that is not recursive enumerable
A language is called recursively enumerable if and only if the language is accepted by some Turing Machine M. In other words L is said to be RE if L = L(M) for some TM M. In this section we will prove that certain language is not recursively enumerable. To prove this we will consider a language consisting a pair (M, w) where:
· M, a Turing Machine with inputs set {0,1}
· W a binary string consisting of 0’s and 1’s.
· M accepts w.
We will make use of three things in this proof and those are:
· Enumerated binary strings
· Coded Turing Machine
· Diagonal language
a.) Enumerating the Binary Strings
We need to assign integers to all binary strings in order to make a relation of binary input with corresponding integer value. For example ε means integer 1, Binary 0 means integer 2, binary 1 means integer 3, binary 00 means integer 4 and binary 01 means integer 5 and so on. The strings should be enumerated, in the sense that these strings should be ordered by length and strings of equal length should be lexicographically ordered. We can refer ith strings as W¡
b.) Codes for Turing Machine
The second important thing that we require in the process of providing a language not a recursively enumerated is binary codes for Turing Machine. After coding a TM by {0,1} we can represent a complete Turing Machine by a sequence of binary string. We can also represent many Turing Machines with the help of binary strings and to identification of the Turing Machine by M¡. The representation of Turing Machine can be M= (Q,{0,1}, Γ, d, q1, B, F) as binary string. To represent the TM by binary strings we first assign binary strings to9 integers of states, tape symbol and directions L and R. Following are the steps used to represent the TM using binary string:
1.) We will assume set of states Q has the states q1, q2,…qk for some k. The start state will always be the q1 and the accept state will be q2. The Turing Machine always halt after entering and accept state and therefore it requires only one accept state.
2.) The tape symbols are X₁, X₂,…Xm for some m. Input symbol X₁ can be represented by 0, X₂ will be by 1 and X₃ by B, the blank. Other tape symbols can be assigned to the remaining integers arbitrarily.
3.) The direction L is represented by D₁ and R can be represented by D₂. The language represented by this TM M can be equivalently represented as L(M)= Ld.
4.) After representation of state, input and directions by binary strings we can encode transition function δ. Suppose one transition rule is δ (q₁, X¡, Dm) where I, j, k, l and m represents integer. This transitions rule can be represented by a binary strings.
c.) Diagonalization Language
As we know that a Turing Machine can be represented by binary string. Hence different Turing Machines can be represented by various binary strings. In other words the ith Turing Machine M¡ whose code is w¡, the ith binary string. To represent various strings corresponding to various TMs we make use of two dimensional arrays ¡ X j. there are many integers that do not correspond to any TM. If w¡ not a valid Turing Machine code then we consider TM M¡ with one state and no transitions. That is, for these values of ¡, the Turing Machine M¡ is such a machine that immediately halts on any input (being one state machine). Thus L (Mi) = 0 if w¡ fails to be valid TM code.
Definition: The diagonalization language, denoted by Ld is a set of strings w¡ such that w¡ is not in L (M¡). Thus Ld consist of all the strings w such that w is not accepted by TM M whose code is w.
1.) Theorem: The diagonalization language Ld is not recursively enumerable language. In other words, there is no such Turing Machine which can accept Ld .
SOURCE: http://books.google.com.ph/books?id=ke0YP7QfRrYC&pg=SA8-PA2&dq=codes+for+turing+machine&hl=en&ei=HozjS9KdF4HCsgPJy-DUBA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CDAQ6AEwAA#v=onepage&q=codes%20for%20turing%20machine&f=false
