Key question
What can a machine compute?
Check your understanding
Find an example, an application and a limit. Explain the concept without using its name, then compare your explanation with a primary source.
Loading your learning…
Claims to examine
Some precisely formulated decision problems have no algorithm that always returns a correct answer.
Follow a learning route
What can a machine compute?
Connect automata, computability, undecidability and complexity through proofs and small executable models.