When is a problem said to be decidable or undecidable?

[shivajikobardan]

Definition 1-:

Taken from here-: https://research.cs.queensu.ca/home/cisc462/moni/m3.pdf

This in my opinion, just makes things complicated. Decision problem is just something where we get output in the form of yes/no…T/F…etc.
But it says it gives input true or false…can you give me example about that?

I thought the goal of decision algorithm should be to find answer in the form of yes or no.

Definition 2-:

Source-: http://www.cs.virginia.edu/~evans/cs302/classes/class17.pdf

This says something else.

Definition 3-:

Source-:

This says something else.

I am confused in this seemingly simple thing. What I feel is that “if there is an algorithm to solve it(basically a turing machine) then it is decidable”...else undecidable. Am I right?

 

[blamocur]

The video is unavailable, but I'll try to respond to written questions.

This in my opinion, just makes things complicated. Decision problem is just something where we get output in the form of yes/no…T/F…etc.
But it says it gives input true or false…can you give me example about that?

Here is an example which fits the definition of "decision function": will this TM terminate on any possible input. It's been proven that this function is undecidable (https://en.wikipedia.org/wiki/Turing's_proof).

I thought the goal of decision algorithm should be to find answer in the form of yes or no.

You thought right. "Yes or No", "True or False" are the same as "truth value" in the definition.

 

[shivajikobardan]

The video is unavailable, but I'll try to respond to written questions.


Here is an example which fits the definition of "decision function": will this TM terminate on any possible input. It's been proven that this function is undecidable (https://en.wikipedia.org/wiki/Turing's_proof).



You thought right. "Yes or No", "True or False" are the same as "truth value" in the definition.

i want to get clarified about decidable and undecidable problems at once.
i think decidable->recursive.
undecidable->if not decidable.
is this final definition ok. there are lots of confusing stuffs like solvable, unsolvable, decidable, undecidable, it is driving me crazy.

 

[blamocur]

I am too rusty on my theory of computations, but if I remember correctly a decidable language means there is a Turing machine which always halts and produces a decision on whether the input belongs to the language.

P.S. Here is another link to add to you confusion : https://en.wikipedia.org/wiki/Theory_of_computation