Difference between computability and decidability

590 views
Hi,

Could someone please tell the difference between computability and decidability?

Thanks

retagged
0
Hi, I wanted to know the diff b/w computability and decidability, not countability . Thanks anyways
0
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.

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

1
212 views
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
$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 )$