Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Computable set
open-in-new
<p>In <a href="/facts/Computability_theory/cqDfXwdf">computability theory</a>, a <a href="/facts/Set_(mathematics)/BfucfHMq">set</a> of <a href="/facts/Natural_number/u65og8JE">natural numbers</a> is called computable, recursive, or decidable if there is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not. </p><p>A set which is not computable is called noncomputable or undecidable. </p><p>A more general class of sets than the computable ones consists of the <a href="/facts/Computably_enumerable/lpzr8jHn">computably enumerable (c.e.) sets</a>, also called semidecidable sets. For these sets, it is only required that there is an algorithm that correctly decides when a number <i>is</i> in the set; the algorithm may give no answer (but not the wrong answer) for numbers not in the set. </p>