The halting problem, which is the set of (descriptions of) Turing machines that halt on input 0, is a well-known example of a noncomputable set.
Problema opririi, care este o mulțime de (descrieri de) mașini Turing care se opresc la intrarea 0, este un exemplu bine-cunoscut de mulțime necalculabilă.