Computability

Limits of computation

Algorithmic complexity limits what can be computed. The amount of processing power and storage available can also limit what can be computed.

Tractable and intractable problems

These are both types of problems that can be solved. Tractable problems can be solved in a reasonable amount of time i.e. polynomial or less. Intractable problems can be solved but not in a reasonable amount of time i.e. exponential time

Heuristic methods

Heuristic solutions are imperfect, but sufficient, solutions that sacrifice perfection for execution speed. They allow for reasonable solutions to be developed to intractable problems e.g. the travelling salesman problem. One such heuristic involves breaking down a large group of towns into smaller clusters of towns in which the solution can be found in polynomial time and then later combine these.

The halting problem

The halting problem asks whether there can be a machine H that for any given program and it’s input can determine if the program will run forever or at some point halt. While it is possible to determine whether a specific program will halt given specific input it is not possible to do so for any program and any input proving some problems are not computable

Knowledge check

This material wil be tested in the Knowledge check on the next page.