The Gateway to Computer Science Excellence
0 votes

Could someone please tell the difference between computability and decidability?

in Theory of Computation by (291 points)
retagged by | 205 views
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

+3 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.





by Active (1.7k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,919 users