Computer Science › Section M · Theory of computation › Topic M.1
Functions and their computation
Every problem a computer solves can be seen as computing a function: turning each input into its one correct output. This topic looks at the ways functions can be computed and opens the big question of section M: are there functions that no machine can ever compute?
What section M asks
Earlier sections showed how computers store data, run programs and follow algorithms. Theory of computation steps back and asks two deeper questions. What can machines compute at all? And of the things they can compute, which can they compute in a reasonable time? The answers are about algorithms, not hardware, so, as far as anyone knows, they hold for today's computers and for any built in the future. The starting point is an idea from mathematics: the function.
Functions in the mathematical sense
A function is a correspondence that assigns to each possible input exactly one output. The collection of possible inputs is the function's domain. Converting Celsius to Fahrenheit is a function: each temperature has one equivalent. So is sorting, which assigns to each list of numbers the same numbers in increasing order, and so is finding the larger of two numbers, whose inputs are pairs. Some functions answer yes or no, such as "is n prime?", which outputs 1 or 0. Computing a function means finding the output for a given input, and solving a problem means computing the function behind it: to sort a list is to compute the sorting function.
Worked example: function or not?
Decide whether each rule is a function. 1. Each student goes to their date of birth. Each has exactly one, so yes; shared birthdays are allowed. 2. Each positive number goes to its square roots. No: 9 would go to both 3 and -3. Choosing only the non-negative root fixes it. 3. Each list of numbers goes to its sorted version. Yes: there is only one correct sorted arrangement. 4. A Python def Roll(N) that returns random.randint(1, N). Not in this sense: calling Roll(6) twice can give different results. Check: in every case the test is whether one input could ever lead to two different outputs.
Everything is a whole number
The inputs and outputs of any program are bit patterns, and any bit pattern can be read as a whole number written in binary, as in "The binary system". A list, a photo or a sentence is just a large number in disguise. The text Hi in ASCII is 01001000 01101001, which read as one binary number is 18,537. So the theory loses nothing by studying functions whose inputs and outputs are non-negative whole numbers.
Method 1: look it up in a table
The simplest way to compute a function is to write every input beside its output and look the answer up. The number of days in each month of a non-leap year fits in a 12-row table: January 31, February 28, and so on. Tables are fast, which is why programs often store precomputed results. But a table only works when the domain is finite. Celsius to Fahrenheit has infinitely many inputs, so any table of it must stop somewhere and is always incomplete.
Method 2: apply a formula
A formula describes infinitely many input and output pairs in one finite line: \(F = \frac{9C}{5} + 32\) converts any Celsius reading, so 37 °C gives 98.6 °F. Formulas have limits too. No finite combination of adding, subtracting, multiplying, dividing and taking roots gives the exact sine of every angle. A calculator or programming library instead carries out a step-by-step approximation, such as adding up terms of a series:
For \(x = 0.5\) radians the three terms give 0.479427, already correct to five decimal places. More powerful functions need a more powerful method.
Method 3: follow an algorithm
An algorithm is the most powerful method: a finite list of steps whose loops repeat as many times as each input needs. Take the function "the Nth prime". No practical formula for it is known, but an algorithm is easy: count upwards, testing each number. Here IsPrime(K) tries dividing K by every whole number from 2 up to its square root.
Worked example: computing the sixth prime
Trace NthPrime(6). 1. K becomes 2, which is prime, so Count = 1. 2. K = 3 is prime, so Count = 2; K = 4 is not. 3. K = 5 gives Count = 3; K = 6 is not prime; K = 7 gives Count = 4. 4. K = 8, 9 and 10 are not prime: 9 fails because 3, its square root, divides it. 5. K = 11 gives Count = 5; K = 12 is not prime; K = 13 gives Count = 6. 6. Now Count < N is false, so the loop stops and the function returns 13. Check: the primes in order are 2, 3, 5, 7, 11, 13, so the sixth is 13.
Computable and noncomputable
A function is computable if some algorithm produces its correct output for every input, finishing each time. Sorting, the larger of two numbers and the Nth prime are all computable. A function that outputs only 1 or 0 is a decision problem, and it is decidable if some algorithm always gives the right answer, undecidable if none does. The striking result of this section is that some perfectly well-defined functions are noncomputable: no algorithm computes them, on any machine, however fast. Undecidable does not mean every input is hard; it means no single algorithm is right for all inputs.
Why noncomputable functions must exist
Every program is a finite text, so all programs can be listed in order: shortest first, alphabetically within each length, as P1, P2, P3 and so on. Now define a yes or no function g: g(n) = 0 if program Pn, given input n, halts with output 1, and g(n) = 1 otherwise. Could some program Pk compute g? At input k, if Pk outputs 1 then g(k) = 0, and if Pk outputs anything else or never stops then g(k) = 1. Either way Pk gets g(k) wrong, so no program on the list computes g. This is a diagonal argument, a method Georg Cantor introduced around 1891. The topic "A noncomputable function: the halting problem" gives a famous example.
Common mistakes to avoid
First, calling a rule a function when one input can give two outputs, as with "the square roots of x". Second, confusing a Python def with a mathematical function: a def that uses random numbers or outside data may return different results for the same input. Third, thinking a formula is needed for a function to be computable: the Nth prime has no practical formula but is easy to compute. Fourth, reading "undecidable" as "no input can be answered"; many inputs may be easy. Fifth, assuming noncomputable just means slow: no amount of time or speed helps.
Key takeaways
A function assigns exactly one output to each input in its domain, and solving a problem means computing a function. All data can be treated as whole numbers. Tables work only for finite domains; formulas cover infinite domains but cannot express every function; algorithms are the most powerful method, with loops that adapt to each input. A function is computable if some algorithm always produces its output; a yes or no problem is decidable if some algorithm always answers it correctly. Because programs can be listed but yes or no functions cannot all be matched to them, noncomputable functions must exist.
Flashcards
Flashcard
A correspondence giving each input exactly one output
Test your understanding
Question 1 of 5
Which of these rules is NOT a function in the mathematical sense?
Question 2 of 5
Using the NthPrime function from the reading, what does NthPrime(4) return?
Question 3 of 5
Why can a table never fully compute the conversion from Celsius to Fahrenheit?
Question 4 of 5
What does it mean to say a decision problem is undecidable?
Question 5 of 5
In the diagonal argument, program P7 given input 7 halts with output 0. What is g(7), and what does it show?
