The Gateway to Computer Science Excellence

0 votes

+1

Sorry! This link might be helpful. https://cs.stackexchange.com/questions/3555/what-is-the-difference-between-decidability-and-computability

0

+3 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 A**lgorithm** 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.**

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,236 comments

104,919 users