Comp Sci When is a problem said to be decidable or undecidable?

  • Thread starter Thread starter shivajikobardan
  • Start date Start date
AI Thread Summary
A decision problem is defined as one that yields a yes/no answer based on specific inputs, which are not inherently true or false but rather represent problems with definitive true or false outcomes. The confusion arises from the distinction between the inputs and the outputs of decision algorithms. For a problem to be decidable, there must exist an algorithm, such as a Turing machine, that can provide a correct answer for all possible inputs within a finite time. If no such algorithm exists, the problem is classified as undecidable. Understanding these definitions is crucial for grasping the complexities of decision problems in computability theory.
shivajikobardan
Messages
637
Reaction score
54
Homework Statement
When is a problem said to be decidable or undecidable?
Relevant Equations
none
Definition 1-:
wtGjGqu-i0wn4WVOCCfvoeFuVtnO9lMPSpKZ_Yxs2ORZPLgD6r.png

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-:
fzHcLn1QUn_om-xDpuG41kpy22GTpqUTWkyNAri5g-xJIA46ab.png

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

This says something else.

Definition 3-:
k6ykZ9EkIDhGTiGQ3QYGzpeB7QKsOqhAdOehkXaKuDIe2ZSDAu.png


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?
 
Physics news on Phys.org
shivajikobardan said:
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
 
  • Like
Likes shivajikobardan

Similar threads

Replies
6
Views
2K
Replies
10
Views
3K
Replies
9
Views
2K
Replies
5
Views
2K
Replies
1
Views
3K
Replies
13
Views
7K
Replies
14
Views
6K
  • Poll Poll
Replies
2
Views
2K
Back
Top