Computability theory (source code)

= 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.