Log In
0 votes

Could someone please tell the difference between computability and decidability?

in Theory of Computation
retagged by
Hi, I wanted to know the diff b/w computability and decidability, not countability . Thanks anyways
If TM halts on valid Input.. that is if the problem is having a logic(Algorithm) then it is computable.. computability comes under REL.

If TM halts on any input (valid or invalid)..  It is a  Halting TM. Then it is decidability. Decidability comes under Recursive language.

1 Answer

4 votes

Computability and Decidability both are same in the sense both of them talk about whether there exist a algorithm or not.


Let us say we have a function 


 if you give it some value of n then it is going to compute n^2+1

Given an i/p if it is going to compute some o/p then that is called function.

if there is a Algorithm to compute a function then such a function is called computable.

Algorithm or TM(halts):-if there exist a TM to which if the i/p is given on its tape then it is going to produce an o/p on the same tape and then it is going to halt for every i/p given 


{Domain:set of number , Range:Set of all a subset positive integer.}

Given a function and Domain if there is a TM which will produce the o/p on the tape and it should definitely halt for every i/p chosen from domain.

eg:-you want to sort all the numbers,Now all the numbers given to the TM, they are all on the tape and now TM should try to sort it out and keep them in ascending order then that is also a function.

if your TM  is able to solve such a function for all the i/p's coming to your domain and it is definitely halt then such a function is called Computable.



we just want to simplify the things 

 Problem:- A statement whose o/p will be either true or false.

Eg- If 'n' is prime 

      n=7 (yes)

      n=10 (no)

if you have such a problem whose answer is either yes or no and if there is a  algorithm or a TM which should definitely halt for all the i/p's from the domain 

{Domain:set of all Natural No.}

 Decidability is easy to apply compared to computability.

whenever we have a domain given any i/p from the domain to TM that TM should definitely halt and say yes or no for such a problem ,if you can find such a TM or if there exist a TM then we can say that the problem is decidable.

Every time a problem is decidable or not that should depend on domain.

Problem:- A given Grammar 'G' is ambiguous 

Domain:-  set of all CFG

this problem is undecidable which means there is no halting TM which can say that a given grammar 'G' is ambiguous.


A particular instance of any problem is always decidable but when it apply to common domain ,it may be decidable or may not be decidable.





edited by

Related questions

0 votes
1 answer
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
asked Aug 13, 2015 in Theory of Computation Anurag_s 212 views
4 votes
2 answers
Please explain clearly?
asked Nov 17, 2016 in Theory of Computation thor 476 views
0 votes
1 answer
$L=\left \{< M_{1},M_{2}> \text{such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$
asked Jul 15, 2019 in Theory of Computation ajaysoni1924 316 views
0 votes
0 answers
please someone explain what are these problems and how to solve these problems for every language with proper explanation? MEMBERSHIP PROBLEM EMPTINESS PROBLEM COMPLETENESS PROBLEM EQUILITY PROBLEM SUBSET PROBLEM DISJOINTNESS PROBLEM IS GIVEN LANGUAGE REGULAR FINITENESS PROBLEM
asked Dec 24, 2018 in Theory of Computation Rahul_Rathod_ 302 views