Jump to content

When is a problem said to be decidable or undecidable?


Recommended Posts

Definition 1-:


 

mKVgfAdOOXQUjpsgw5h2pGNfVLLZHC8ZEZ3up_Gtxosm_TrMaYWg7qPbYhyx72qEwW3z__qp6Ls3fhnPSwDCa9wtGjGqu-i0wn4WVOCCfvoeFuVtnO9lMPSpKZ_Yxs2ORZPLgD6r

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

LGJ5Mw19XOGQUgfSwqofQnzI53tDpmI4OPyyQscQ0oGdRPVp1VNNM7xOEqX0uzvN0saBrShn3CYHGUDhxr1qFrfzHcLn1QUn_om-xDpuG41kpy22GTpqUTWkyNAri5g-xJIA46ab

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

 

This says something else.

 

Definition 3-:

SoyiGloVOdLygjH1CcFeh5Hu_KHSr7aFVjQVZj7QNdi9JXsshYGXaIz6bVJ-ahW4B9kB7ji7DeDgLS5uWnHj3Ek6ykZ9EkIDhGTiGQ3QYGzpeB7QKsOqhAdOehkXaKuDIe2ZSDAu

 

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?

Link to comment
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.

Link to comment
Share on other sites

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
Link to comment
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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
 Share

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.