Intro
Objectives
- Be aware that algorithmic complexity and hardware impose limits on what can be computed.
- Know that algorithms may be classified as being either tractable or intractable.
- Be aware that some problems cannot be solved algorithmically.
- Describe the Halting problem, and understand its significance for computation.
Resources
Videos
Tractable vs. intractable
The halting problem