Home›Science›Computer Science (Theory)›What is Decidability?
◉ Science·2 min·Updated Mar 12, 2026

What is Decidability?

Decidability

Quick Answer

Decidability refers to whether a problem can be solved by an algorithm in a finite amount of time. If a problem is decidable, there exists a clear method to determine the answer for any input. If it is undecidable, no such method exists.

Overview

Decidability is a concept in computer science that deals with whether a specific problem can be solved algorithmically. In simple terms, a problem is decidable if there is a systematic way to arrive at a solution within a finite time frame for any possible input. For example, determining whether a number is even or odd is a decidable problem because we can create an algorithm that checks this condition quickly and reliably. On the other hand, some problems are undecidable, meaning no algorithm can solve them for all possible inputs. A classic example is the Halting Problem, which asks whether a given program will eventually stop running or continue indefinitely. Alan Turing proved that there is no general algorithm that can solve this problem for all possible programs, highlighting the limits of what can be computed. Understanding decidability is crucial in computer science because it helps researchers and developers know the boundaries of algorithmic problem-solving. This knowledge guides the design of algorithms and informs the development of software systems, ensuring that resources are allocated efficiently and effectively when tackling computational challenges.

Frequently Asked Questions

An example of a decidable problem is checking if a number is prime. There are algorithms that can determine whether a number has any divisors other than one and itself, allowing us to conclude if it is prime in a finite amount of time.
The Halting Problem is important because it illustrates the limitations of computation. Turing's proof that no algorithm can solve this problem for all cases shows that some questions are fundamentally beyond the reach of algorithmic solutions.
Decidability impacts computer programming by helping programmers understand which problems can be solved efficiently. It encourages the use of algorithms for decidable problems while recognizing that some problems may require alternative approaches or approximations.