When is a problem said to be decidable or undecidable?

[shivajikobardan]

Homework Statement

When is a problem said to be decidable or undecidable?

Relevant Equations

none

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?

 

[Mark44]

But it says it gives input true or false…can you give me example about that?

That's not what the 2nd bullet of Def. 1 says:

A decision algorithm is an algorithm that computes the correct truth value for each input instance of a decision problem. The algorithm has to terminate on all inputs!

The inputs are not true or false. The inputs are problems that have answers that are true or false.

For an extensive list of undecidable problems, see https://en.wikipedia.org/wiki/List_...wer.?msclkid=ba518877c26211eca77096aa5f91dd81