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?
In this topic
- What section M asks
- Functions in the mathematical sense
- Worked example: function or not?
- Everything is a whole number
- Method 1: look it up in a table
- Method 2: apply a formula
- Method 3: follow an algorithm
- Worked example: computing the sixth prime
- Computable and noncomputable
- Why noncomputable functions must exist
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…