- #1

shivajikobardan

- 674

- 54

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-:

https://lh4.googleusercontent.com/LGJ5Mw19XOGQUgfSwqofQnzI53tDpmI4OPyyQscQ0oGdRPVp1VNNM7xOEqX0uzvN0saBrShn3CYHGUDhxr1qFrfzHcLn1QUn_om-xDpuG41kpy22GTpqUTWkyNAri5g-xJIA46ab

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

This says something else.

Definition 3-:

https://lh6.googleusercontent.com/SoyiGloVOdLygjH1CcFeh5Hu_KHSr7aFVjQVZj7QNdi9JXsshYGXaIz6bVJ-ahW4B9kB7ji7DeDgLS5uWnHj3Ek6ykZ9EkIDhGTiGQ3QYGzpeB7QKsOqhAdOehkXaKuDIe2ZSDAu

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?