algorithms

References

Summary

We can think of algorithms as certain kinds of partial functions (of course that's just a total function once you restrict the domain)

Every program has an assosciated partial function

Definitions

Computable Functions

These are supposed to be all of the functions on N that can be computed in principle

These are also called partial recursive functions

Ex: Non-Computable

The Halting Problem Hilbert's 10th problem Entscheidungsproblem