What can be computed, and what cannot.
Answer five questions about Computability Theory and get instant feedback.
A yes or no question that no algorithm can answer correctly for every input
The classic example is the halting problem: given any program and input, no algorithm can always decide whether it will eventually stop or run forever.
What kind of problem has an algorithm that halts on every input and answers yes or no?
Many classic tasks like testing if a number is prime are decidable, and the big mystery in computability is telling which problems are decidable and which are doomed to never halt.
This image question appears in the interactive quiz.
A Turing machine separates computation into memory, rules, and step-by-step symbol changes.
All computable sets sit in the same Turing degree, often called ...
Degree $\mathbf{0}$ is the bottom of the Turing degree structure, and the next landmark $\mathbf{0'}$ is the degree of the halting problem, showing a strict jump in computational power.
A many-one reduction guarantees that decidability of the source problem implies decidability of the target problem.
A many-one reduction guarantees that decidability of the target problem implies decidability of the source problem. If $A \le_m B$ and $B$ is decidable, decide $A$ by mapping $x \mapsto f(x)$ and running the decider for $B$, so reductions transfer decidability backward, not forward.
Learn and play with MAGMA Mentor to build your understanding step by step.