retagged by
2,589 views
0 votes
0 votes
Hi,

Could someone please tell the difference between computability and decidability?

Thanks
retagged by

1 Answer

6 votes
6 votes

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

COMPUTABILITY

Let us say we have a function 

f(n)=n^2+1

 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 

or

{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.

 

DECIDABILITY

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
0 votes
1 answer
1
Anurag_s asked Aug 13, 2015
369 views
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
4 votes
4 votes
2 answers
2
thor asked Nov 16, 2016
1,030 views
Please explain clearly?