A function can be computable even if no real computer could ever finish it
In mathematical logic, computable does not mean practical. A function counts as computable if some finite set of instructions produces its answer eventually, with unlimited time and as much memory as it asks for. Inputs larger than the number of atoms in the Earth are allowed, and some computable functions take exponentially longer as their inputs grow.
Before anyone defined the term precisely, mathematicians spoke of functions being effectively calculable. Formalising the idea required picking a model of computation, and several very different ones were proposed: Turing machines, register machines, Church's lambda calculus and general recursive functions. Remarkably, all four capture exactly the same set of functions, and every other model ever suggested has turned out to compute nothing beyond them. Each can imitate the others, much as a compiler translates one programming language into another.
That convergence underpins the Church–Turing thesis, the claim that no conceivable notion of computation can exceed this class. It cannot be proved, because the informal idea of an algorithm has no precise definition to prove it against. The habit of calling these functions recursive traces to a 1934 discussion between Stephen Kleene and Kurt Gödel.
Herbert Enderton's 1977 description, echoing Turing and others, sets out the rules. The instructions must be exact and finite, needing no guesswork or special insight. Given a valid input, the procedure must stop after finitely many discrete steps and output the answer. Given an input outside its domain, it may run forever or get stuck, but it must never hand back a wrong value.
Efficiency is a separate question. Computational complexity studies what can be done within set limits on time or memory, whereas computability only asks whether an answer is reachable at all. The same thinking applies to sets and languages. A set of numbers is decidable if a procedure can always answer yes or no to membership, and merely enumerable if some procedure can list all its members without ever ruling anything out.
Source: Computable function
