# When is a problem said to be decidable or undecidable?

## Recommended Posts

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

This says something else.

Definition 3-:

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?

##### Share on other sites

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.

##### Share on other sites

Posted (edited)
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 by dimreepr
##### Share on other sites

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.

## Create an account

Register a new account