Computability and Decidability

Both computability and decidability are same ,both of them talk about whether their exist a algorithm or not.

1)Algorithm is nothing but tuning machine ,but this TM is suppose to halt. Algorithm<--->TM(Halt)

but reverse is not true.Only halting tuning machine are consider as algo .

2)Halting tuning machine are subset of tuning machine and we know subset of any countable set is also countable. here we know all language are not countable and every problem can be compair to a language.Now no of problem are uncountable.As we know no of algo are countable therefore,what could be derive is that there are some problem for which algo might not be exist.


Countable set:

A set 'S' is said to be countable ,if all the element of these set can be put in one to one correspondence with the set of natural number.


Uncountable  set:

A set 'S' is said to be Uncountable ,if it is infinite and not countable.


for example , every element in even no we can give a element from the natural no as correspondence so we can say even no is countable.



Set of all real no is uncountable.


Alternative definition of countability:

A set is said to be countable if there exist an enumeration method using which all the element of set can be generated ,and for any particular element ,it takes only finite number of stapes to generate it.


            The finite number of step takes to generate an element can be used as its index and hence a mapping into natural number.


here are some set of element which are countable :

1)set of all quotients are countable.

2)set of all string over any finite alphabet are countable i.e ∑={a.b}



Every subset of countable set is either finite or countable.


3)set of all turing machine are countable.

as we know,

                a)∑*={ε,a,b,aa,ab,ba,ba,......................................} is countable

                b)every turing machine can be encoded as a string of 0's and 1's.

                 c)set of all turing machine,S⊆∑*

                 d)Every subset of countable set is either finite or countable.

by using these rule we can say that set of all turing machine are countable.


here we should know that set of all language are uncountable.




If S1 and S2 are countable sets then S1 union S2 is countable and S1*S2 is countable.


1)The cartesian product of finite number of countable sets is countable.

2)The set of all language that are not recursively enumerable is uncountable.