What It Means for a Machine to Compute a Function
In computer science, a function is a rule that takes an input and specifies an output. A machine computes it when a precise procedure can turn each valid input into the corresponding answer. The procedure might be a short formula, a sequence of arithmetic operations, or a longer algorithm that branches according to what it finds.
Theoretical models such as the Turing machine make this idea exact. A Turing machine is an intentionally simple description of a computer: it reads and writes symbols on a tape and follows a fixed set of rules. Despite its simplicity, it can represent the essential logic of ordinary computation. Saying that a function is computable means that some such procedure gives the correct result for every input in its domain—not that the procedure is practical.
A Recipe Is Not the Same as a Finished Calculation
An algorithm may be guaranteed to produce an answer eventually while requiring an enormous amount of time or memory. For example, a procedure might need to examine possibilities whose number grows so quickly with the input that even a modestly larger case becomes unreachable. The function remains computable, but the machine may not finish before its resources run out.
There is also a deeper limit: some well-defined questions cannot be settled by any algorithm that always halts with the right answer. The classic halting problem asks whether a given program will eventually stop or run forever. No general-purpose procedure can correctly decide that for every possible program and input. This is not a matter of insufficient speed; it is a limit on what a step-by-step method can accomplish.
Why the Distinction Matters
Computability asks whether a reliable recipe exists. Complexity asks how much time and memory that recipe needs. Keeping those questions separate helps explain why a computer can solve some problems only on small inputs, while other questions resist a universal algorithm altogether. A precise mathematical question can therefore have a clear meaning—and still have no machine-made answer in every case.
