= Computability theory
{wiki}
= Recursion theory
{synonym}
<Computability theory> asks which tasks can be performed by an <algorithm>, and which cannot, using precise models such as <Turing machines> and <recursive functions>. It distinguishes a total <computable function>, which returns an answer on every input, from a partial one, which may never halt on some inputs.
The <halting problem> is the central limitation: no <algorithm> decides for every encoded program and input whether that computation eventually stops. Nevertheless, halting instances can be enumerated by simulating computations for successively longer times. This illustrates the distinction between a <computable set> and a <computably enumerable set>. The subject concerns the existence of computation; <computational complexity theory> further asks how much time or space a computation needs.
Back to article page