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-: https://www.youtube.com/watch?v=WdWbi5-OIy8

 

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?

[fiveworlds]

Turing's definition of decidable and undecidable algorithms is basically if the algorithm never halts then it is undecidable.

Take a chess board with 2 rooks black and white. Neither player will ever move into a position where their rook can be taken so ultimately it is undecidable.

This definition is limited because we have things like screen update functions. They will constantly draw images to your screen as well but can be shutdown by external input but not by halting themselves.

[dimreepr]

14 hours ago, fiveworlds said:

Turing's definition of decidable and undecidable algorithms is basically if the algorithm never halts then it is undecidable.

Take a chess board with 2 rooks black and white. Neither player will ever move into a position where their rook can be taken so ultimately it is undecidable.

This definition is limited because we have things like screen update functions. They will constantly draw images to your screen as well but can be shutdown by external input but not by halting themselves.

There's always a get out clause in any algorithm, a limited counter with a least objectionable outcome.

Edited April 24, 2022 by dimreepr

[Sensei]

On 4/24/2022 at 3:40 PM, dimreepr said:

There's always a get out clause in any algorithm, a limited counter with a least objectionable outcome.

Sometimes a programmer creates an infinite loop (e.g. Thread.Sleep( Timeout.Infinite ); https://www.google.com/search?q=thread.sleep+infinite ) in a child thread and terminates it from another ("parent") thread. This avoids having pointers to threads which already completed their work from mixing with those that are still busy..

Hackers/criminals often use infinite loops, such as for DDoS or resource abuse. They don't care about code cleanliness.